{ }codelper
dynamic memoryP0158

An array that doubles

Build a growable array of integers yourself. The array keeps the number of elements (its size) separately from the number of slots it has borrowed memory for (its capacity). At the start the size is 0 and the capacity is 1. There are four commands. - push x: if the size equals the capacity, first double the capacity (one grow), then append x at the end. - pop: if the array is empty, print empty.
Otherwise remove the last value and print it; after that, if the capacity is at least 2 and size×4 is at most the capacity, halve the capacity (one shrink). - get i: print the value at index i, counting from 0.
If i is at least the size, print out of range. - info: print the size and the capacity separated by one space. The first line gives the number of commands q, and the next q lines give one command each. Print the output above for each command, one line each, and on the last line print "grow number_of_grows shrink number_of_shrinks". The capacity that info prints is always the value given by the rules above. In C, resize the borrowed block with realloc; in C++, keep count of the capacity yourself in a variable and borrow that much ahead of time with std::vector's reserve.

Input
1 ≤ q ≤ 100,000, -1,000,000,000 ≤ x ≤ 1,000,000,000, 0 ≤ i ≤ 100,000 (integers)
Output
one line for each command other than push, then "grow G shrink S"
Example 1 · stdin
9
push 4
push 8
push 15
info
get 2
pop
pop
info
get 1
stdout
3 4
15
15
8
1 2
out of range
grow 2 shrink 1
main.py
Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 2 languages

This problem accepts only C and C++.
Choosing how many slots to borrow and moving the data yourself is their job; Python list, JS arrays, Java ArrayList, C# List<T> and Craykon lists grow on their own (the factor differs by implementation: OpenJDK's Java ArrayList grows by 1.5×, .NET's C# List<T> by 2×).
In C, realloc(p, newcap * sizeof *p) grows or shrinks the block, and if it can't grow in place it moves the data to a new place and returns the new address.
On failure it returns NULL and the old block is untouched, so overwriting directly as in v->data = realloc(v->data, ...) loses the old block.
Check the returned pointer separately before storing it.
A C++ std::vector also keeps its size size() and capacity capacity() separately, and reserve(n) widens it ahead of time.
But the standard only promises that the capacity is at least n after reserve(n), and the factor by which push_back grows on its own differs between standard libraries (2× in libstdc++ and libc++, 1.5× in MSVC).
So the C++ solution counts this problem's capacity itself in a variable cap and uses reserve(cap) to borrow at least that much.
Doubling makes moves rare, so one push costs O(1) on average.
Four traps: ① Growing one slot at a time moves the data on every push, O(q²) in total, and the capacities differ from this problem's answer.
② Shrinking as soon as the size reaches half the capacity makes push/pop at the boundary grow and shrink again and again.
Waiting until a quarter and then halving leaves half the slots free after the shrink.
③ In C++, trusting capacity() as the capacity instead of counting it yourself goes wrong at the shrink.
reserve cannot reduce the capacity: given a smaller value it does nothing.
To really give the slots back, move the elements into a new vector that reserved half and swap.
shrink_to_fit() is a (non-binding) request to fit the size exactly, not to halve.
④ std::vector<int> v(1) does not borrow one slot; it creates one element holding 0.
To borrow a slot while staying empty, use v.reserve(1).

C++main.cpp · 53 lines
#include <iostream>#include <string>#include <vector> int main() {    std::ios::sync_with_stdio(false);    // 용량은 이 문제의 규칙대로 직접 센다.    // capacity()가 돌려주는 값은 표준 라이브러리마다 다를 수 있다(reserve(n) 뒤에는 n 이상이라는 것만 약속된다).    std::size_t cap = 1;    std::vector<int> v;    v.reserve(cap);  // 크기(size)는 0인 채로 적어도 cap칸을 빌려 둔다    int grow = 0, shrink = 0;    int q;    std::cin >> q;    std::string cmd;    for (int i = 0; i < q; i++) {        std::cin >> cmd;        if (cmd == "push") {            int x;            std::cin >> x;            if (v.size() == cap) {  // 가득 찼으면 두 배로: 늘리는 때를 직접 정한다                cap *= 2;                v.reserve(cap);                grow++;            }            v.push_back(x);  // capacity()가 cap 이상이라 여기서는 다시 옮겨 담지 않는다        } else if (cmd == "pop") {            if (v.empty()) {                std::cout << "empty\n";                continue;            }            std::cout << v.back() << '\n';            v.pop_back();  // 크기만 줄고 빌린 칸은 그대로다            if (cap > 1 && v.size() * 4 <= cap) {                cap /= 2;                // reserve는 칸을 줄이지 못한다: 반만큼 빌린 새 vector에 옮겨 담고 맞바꾼다                std::vector<int> smaller;                smaller.reserve(cap);                smaller.assign(v.begin(), v.end());                v.swap(smaller);                shrink++;            }        } else if (cmd == "get") {            std::size_t k;            std::cin >> k;            if (k < v.size()) std::cout << v[k] << '\n';            else std::cout << "out of range\n";        } else {            std::cout << v.size() << ' ' << cap << '\n';        }    }    std::cout << "grow " << grow << " shrink " << shrink << '\n';}
Cmain.c · 68 lines
#include <stdio.h>#include <stdlib.h>#include <string.h> /* 직접 만든 늘어나는 배열: data는 cap칸을 빌려 두고, 앞의 size칸만 쓴다 */typedef struct {    int *data;    int size, cap;    int grow, shrink;} IntVec; /* 칸 수를 newcap으로 바꾼다. realloc은 자리를 옮길 수 있어서 돌려받은 포인터를 쓴다 */static void resize(IntVec *v, int newcap) {    int *p = realloc(v->data, (size_t)newcap * sizeof *p);    if (p == NULL) {             /* 실패하면 옛 블록은 그대로 남아 있다 */        free(v->data);        exit(1);    }    v->data = p;    v->cap = newcap;} static void push(IntVec *v, int x) {    if (v->size == v->cap) {     /* 가득 찼으면 두 배로: 옮겨 담기가 드물어진다 */        resize(v, v->cap * 2);        v->grow++;    }    v->data[v->size++] = x;} /* 빈 배열이면 0, 아니면 *out에 마지막 값을 꺼내고 1 */static int pop(IntVec *v, int *out) {    if (v->size == 0) return 0;    *out = v->data[--v->size];    if (v->cap > 1 && v->size * 4 <= v->cap) {  /* 1/4 이하로 줄면 반으로 */        resize(v, v->cap / 2);        v->shrink++;    }    return 1;} int main(void) {    IntVec v = { NULL, 0, 0, 0, 0 };    resize(&v, 1);               /* 처음에 한 칸 빌려 둔다 */    int q;    scanf("%d", &q);    for (int i = 0; i < q; i++) {        char cmd[8];        int x;        scanf("%7s", cmd);        if (strcmp(cmd, "push") == 0) {            scanf("%d", &x);            push(&v, x);        } else if (strcmp(cmd, "pop") == 0) {            if (pop(&v, &x)) printf("%d\n", x);            else puts("empty");        } else if (strcmp(cmd, "get") == 0) {            scanf("%d", &x);            if (x < v.size) printf("%d\n", v.data[x]);            else puts("out of range");        } else {            printf("%d %d\n", v.size, v.cap);        }    }    printf("grow %d shrink %d\n", v.grow, v.shrink);    free(v.data);                /* 빌린 블록은 마지막에 한 번 돌려준다 */    return 0;}