{ }codelper
pointersP0246

A box ranking built from an array of pointers

There are n boxes numbered 1 to n, and box i weighs w_i. The ranking has n slots, and each slot points to one box.
At first, slot r points to box r. There are five commands. - sort: rebuild the ranking.
Slots pointing to heavier boxes come first; for equal weights, the box with the smaller number comes first. - add r v: add v to the weight of the box that slot r of the ranking points to.
The ranking is not rebuilt. - swap i j: exchange the weights of box i and box j.
The slots of the ranking keep pointing to the same numbered boxes.
i and j may be equal, in which case nothing changes. - who r: print on one line the number of the box that slot r of the ranking points to. - show: print on one line the n weights of the boxes the slots point to, from the first slot on, separated by single spaces. The first line gives n and q, the second line gives w_1 to w_n, and the next q lines give one command each. Try keeping the weights in an array int w[n] and making the ranking an array of pointers int *rank[n] into it. For sort, do not move the weights: arrange only the pointers with qsort (std::sort in C++). For equal weights compare the two pointers themselves, and for who find the number by pointer subtraction rank[r - 1] - w. Write swap as a function void swap_weight(int *a, int *b) that receives the addresses of the two slots.

Input
1 ≤ n ≤ 1,000, 1 ≤ q ≤ 2,000, 1 ≤ r, i, j ≤ n.
Weights and v are integers; at the start and after every add, every weight is between -2,000,000,000 and 2,000,000,000 (|v| is within this range too).
All show commands together print at most 15,000 numbers.
who or show appears at least once.
Output
One line per who and per show
Example 1 · stdin
4 10
5 -2 5 7
sort
show
who 2
add 4 10
swap 1 2
show
sort
show
who 3
swap 3 3
stdout
7 5 5 -2
1
7 8 5 5
8 7 5 5
2
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++.
Pointers that hold an address as a value, subtracting pointers to get how many slots apart they are, and comparing addresses by size exist only in those two languages.
In Python, JavaScript, TypeScript, Java, C# and Craykon the same job is done by storing box numbers (positions) in the ranking and reaching them with w[rank[r]] (real pointers in C# live only inside unsafe).
C's qsort passes the comparison function the addresses of the slots being sorted as const void *.
Each slot holds an int *, so unwrapping once with *(int *const *)pa gives the pointer, and unwrapping again (*a) gives the weight.
C++ std::sort hands its comparison two const int * directly.
Two pointers into the same array can be compared with < (a smaller address means a smaller number), and subtracting them gives the number of slots between them (rank[r - 1] - w + 1 is the box number).
Five traps: (1) Unwrapping only once in the comparison, as in *(const int *)pa, compares part of the pointer value instead of the weight, so the order is garbage.
(2) return *b - *a; flips sign when the difference exceeds the int range (about 2.1 billion), as in 2e9 - (-2e9).
Compare and return -1 or 1.
(3) Swapping without a temporary as *a ^= *b; *b ^= *a; *a ^= *b; turns the weight into 0 when a and b are the same slot (swap 3 3).
Always remember that two pointers can point to the same place (aliasing).
(4) Storing copies of the weights in the ranking instead of pointers makes add change only the copy, and swap never shows up in the ranking.
(5) Leaving equal weights to C++ std::stable_sort instead of breaking ties by number keeps the current ranking order after add and swap, not the original numbering.

C++main.cpp · 51 lines
#include <algorithm>#include <iostream>#include <string>#include <utility>#include <vector> // a와 b가 같은 칸을 가리켜도 맞게 바꾼다void swap_weight(int *a, int *b) {    int tmp = *a;    *a = *b;    *b = tmp;} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n, q;    std::cin >> n >> q;    std::vector<int> w(n);    // 상자의 무게. 크기를 다시 바꾸지 않으니 포인터가 계속 맞다    std::vector<int *> rank(n); // 순위표: 칸마다 w의 한 칸을 가리킨다    for (int i = 0; i < n; i++) {        std::cin >> w[i];        rank[i] = &w[i];    }    for (int k = 0; k < q; k++) {        std::string cmd;        std::cin >> cmd;        if (cmd == "sort") {            std::sort(rank.begin(), rank.end(), [](const int *a, const int *b) {                if (*a != *b) return *a > *b;                return a < b; // 무게가 같으면 주소(= 번호)가 작은 쪽이 앞            });        } else if (cmd == "add") {            int r, v;            std::cin >> r >> v;            *rank[r - 1] += v;        } else if (cmd == "swap") {            int i, j;            std::cin >> i >> j;            swap_weight(&w[i - 1], &w[j - 1]);        } else if (cmd == "who") {            int r;            std::cin >> r;            std::cout << (rank[r - 1] - w.data()) + 1 << '\n';        } else {            for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << *rank[i];            std::cout << '\n';        }    }    return 0;}
Cmain.c · 53 lines
#include <stdio.h>#include <stdlib.h>#include <string.h> static int w[1000];     /* 상자의 무게: w[0]이 1번 상자 */static int *rank[1000]; /* 순위표: 칸마다 w의 한 칸을 가리킨다 */ /* qsort는 늘어놓을 칸의 주소를 const void *로 준다. 칸에 든 것이 int *이니 진짜 타입은 int *const * */static int heavier_first(const void *pa, const void *pb) {    const int *a = *(int *const *)pa;    const int *b = *(int *const *)pb;    if (*a != *b) return *a > *b ? -1 : 1; /* 빼기(*b - *a)는 int를 넘칠 수 있다 */    return (a > b) - (a < b);              /* 같은 배열 안의 포인터는 크기를 비교할 수 있다: 주소가 작으면 번호도 작다 */} /* a와 b가 같은 칸을 가리켜도 맞게 바꾼다(임시 변수) */static void swap_weight(int *a, int *b) {    int tmp = *a;    *a = *b;    *b = tmp;} int main(void) {    int n, q;    char cmd[8];    scanf("%d %d", &n, &q);    for (int i = 0; i < n; i++) {        scanf("%d", &w[i]);        rank[i] = &w[i];    }    for (int k = 0; k < q; k++) {        scanf("%7s", cmd);        if (strcmp(cmd, "sort") == 0) {            qsort(rank, n, sizeof rank[0], heavier_first);        } else if (strcmp(cmd, "add") == 0) {            int r, v;            scanf("%d %d", &r, &v);            *rank[r - 1] += v; /* 가리키는 상자의 무게가 바뀐다 */        } else if (strcmp(cmd, "swap") == 0) {            int i, j;            scanf("%d %d", &i, &j);            swap_weight(&w[i - 1], &w[j - 1]);        } else if (strcmp(cmd, "who") == 0) {            int r;            scanf("%d", &r);            printf("%d\n", (int)(rank[r - 1] - w) + 1); /* 포인터 빼기 = 몇 칸 떨어져 있나 */        } else {            for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", *rank[i]);            printf("\n");        }    }    return 0;}