{ }codelper
dynamic memoryP0202

A table whose rows have different lengths

There is a table that holds integers.
Each row of the table may hold a different number of values, and some rows hold no values at all. At first the table has no rows.
Rows are numbered from 1. There are six commands. - new k v1 … vk: attach a new row holding k values at the bottom of the table.
k can be 0. - copy i: attach a new row holding the same values as row i at the bottom of the table.
After that the two rows change independently. - add i v: append one value v to the end of row i. - set i j v: change the j-th value (counted from 1) of row i to v. - del i: delete row i.
The rows below it move up by one number each. - print i: print on one line the number of values k in row i followed by the k values, separated by single spaces.
If the row is empty, print just 0. The row numbers and value positions in commands always exist. The first line gives the number of commands q, and the next q lines give one command each. Print one line for each print, and on the last line print the number of remaining rows and the number of values in the whole table, separated by a single space. Try allocating memory separately for each row, as much as it needs (malloc, realloc and free in C, std::vector<std::vector<int>> in C++). copy allocates a new block and copies the values into it, and del gives that row's block back.

Input
1 ≤ q ≤ 50,000, -10⁹ ≤ v ≤ 10⁹.
The k values of all new commands add up to at most 100,000.
At any time the table has at most 5,000 rows and holds at most 500,000 values in all, the values copied by copy add up to at most 500,000, and the values printed by print add up to at most 30,000.
Output
One line per print, then a last line "rows values"
Example 1 · stdin
9
new 3 1 2 3
copy 1
set 2 1 9
add 1 4
new 0
add 3 -5
del 2
print 1
print 2
stdout
4 1 2 3 4
1 -5
2 5
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++.
Allocating and freeing memory for each row yourself is the job of those two languages; lists in Python, JavaScript, TypeScript, Java, C# and Craykon grow on their own and the garbage collector cleans up (those languages still need a separate copy for copy, such as row[:], [...row], new ArrayList<>(row) or new List<int>(row)).
C keeps a struct per row with int *data, a length and a capacity, and allocates the table holding the rows as a Row * too, so it allocates in two layers.
When growing, check the pointer realloc returns before storing it, and since del shifts overlapping slots after free(data), use memmove, not memcpy.
Reallocating the table may move its block, so get pointers like &t.rows[i] again after doing it.
At the end, free each row and then free the table.
In C++, std::vector handles allocating, growing and freeing (RAII), and copying as in std::vector<int> dup = rows[i]; moves all values into a new block.
Four traps: ① In C, assigning the struct as in t.rows[n] = t.rows[i]; copies only the data pointer, so the two rows share one block.
A set on one changes the other too, and at the end the same block is freed twice and the program stops.
② The third argument of memcpy(dst, src, len) is a number of bytes, not of slots.
It must be len * sizeof(int); passing just len copies only the first quarter.
③ In C++, auto row = rows[i]; row.push_back(v); appends to a copy.
To change the original, use auto &row.
④ In C++, writing row[j] after row.reserve(k) leaves the row empty, because reserve only grows the capacity and the size stays 0.
Create the slots with std::vector<int> row(k) or resize(k).

C++main.cpp · 45 lines
#include <iostream>#include <string>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    // 바깥 vector가 줄들을, 안쪽 vector가 줄마다 값들을 빌려 쥔다. 지워지면 알아서 돌려준다(RAII)    std::vector<std::vector<int>> rows;    int q;    std::cin >> q;    std::string cmd;    while (q--) {        std::cin >> cmd;        int i, j, k, v;        if (cmd == "new") {            std::cin >> k;            std::vector<int> row(k);  // 크기 k: 칸이 k개 생긴다(reserve는 칸을 만들지 않는다)            for (int &x : row) std::cin >> x;            rows.push_back(std::move(row));        } else if (cmd == "copy") {            std::cin >> i;            std::vector<int> dup = rows[i - 1];  // vector 복사는 새 블록을 빌려 값을 모두 옮긴다(깊은 복사)            rows.push_back(std::move(dup));        } else if (cmd == "add") {            std::cin >> i >> v;            rows[i - 1].push_back(v);        } else if (cmd == "set") {            std::cin >> i >> j >> v;            rows[i - 1][j - 1] = v;        } else if (cmd == "del") {            std::cin >> i;            rows.erase(rows.begin() + (i - 1));  // 그 줄의 블록을 돌려주고 뒤를 당긴다        } else {            std::cin >> i;            const auto &row = rows[i - 1];            std::cout << row.size();            for (int x : row) std::cout << ' ' << x;            std::cout << '\n';        }    }    long long cells = 0;    for (const auto &row : rows) cells += row.size();    std::cout << rows.size() << ' ' << cells << '\n';}
Cmain.c · 98 lines
#include <stdio.h>#include <stdlib.h>#include <string.h> typedef struct {    int *data; /* 이 줄의 값들을 담으려고 빌린 블록 */    int len;   /* 들어 있는 값의 수 */    int cap;   /* 빌린 칸의 수 */} Row; typedef struct {    Row *rows;    int n, cap;} Table; /* 빌리기에 실패하면 멈춘다(받은 포인터를 확인한 다음에 담는다) */static void *grow(void *p, size_t count, size_t size) {    void *q = realloc(p, count * size);    if (q == NULL) {        fprintf(stderr, "out of memory\n");        exit(1);    }    return q;} /* 표 끝에 빈 줄 자리를 하나 만들어 그 주소를 돌려준다.   표의 블록이 옮겨질 수 있으니, 이 함수를 부르기 전에 쥔 Row 포인터는 부른 뒤에 쓰지 않는다 */static Row *append_row(Table *t, int cap) {    if (t->n == t->cap) {        t->cap = t->cap ? t->cap * 2 : 4;        t->rows = grow(t->rows, (size_t)t->cap, sizeof *t->rows);    }    Row *r = &t->rows[t->n++];    r->len = 0;    r->cap = cap > 0 ? cap : 1;    r->data = malloc((size_t)r->cap * sizeof *r->data);    if (r->data == NULL) exit(1);    return r;} static void push(Row *r, int v) {    if (r->len == r->cap) {        r->cap *= 2;        r->data = grow(r->data, (size_t)r->cap, sizeof *r->data);    }    r->data[r->len++] = v;} int main(void) {    Table t = {NULL, 0, 0};    int q, i, j, k, v;    char cmd[8];    if (scanf("%d", &q) != 1) return 0;    while (q--) {        scanf("%7s", cmd);        if (strcmp(cmd, "new") == 0) {            scanf("%d", &k);            Row *r = append_row(&t, k);            for (j = 0; j < k; j++) {                scanf("%d", &v);                push(r, v);            }        } else if (strcmp(cmd, "copy") == 0) {            scanf("%d", &i);            int len = t.rows[i - 1].len;            Row *dst = append_row(&t, len);  /* 먼저 자리를 만들고 */            const Row *src = &t.rows[i - 1]; /* 그다음 원본 주소를 쥔다 */            memcpy(dst->data, src->data, (size_t)len * sizeof *src->data); /* 바이트 수 = 칸 수 × 칸 크기 */            dst->len = len;        } else if (strcmp(cmd, "add") == 0) {            scanf("%d %d", &i, &v);            push(&t.rows[i - 1], v);        } else if (strcmp(cmd, "set") == 0) {            scanf("%d %d %d", &i, &j, &v);            t.rows[i - 1].data[j - 1] = v;        } else if (strcmp(cmd, "del") == 0) {            scanf("%d", &i);            free(t.rows[i - 1].data);            /* 뒤의 줄들을 한 칸씩 당긴다: 겹치는 자리라 memcpy가 아니라 memmove */            memmove(&t.rows[i - 1], &t.rows[i], (size_t)(t.n - i) * sizeof *t.rows);            t.n--;        } else {            scanf("%d", &i);            const Row *r = &t.rows[i - 1];            printf("%d", r->len);            for (j = 0; j < r->len; j++) printf(" %d", r->data[j]);            printf("\n");        }    }    long long cells = 0;    for (i = 0; i < t.n; i++) {        cells += t.rows[i].len;        free(t.rows[i].data); /* 줄마다 빌린 블록을 돌려주고 */    }    free(t.rows); /* 마지막으로 표의 블록을 돌려준다 */    printf("%d %lld\n", t.n, cells);    return 0;}