1 番から n 番までの箱が n 個あり、i 番の箱の重さは w_i である。 順位表は n 枠で、枠ごとに箱を一つ指している。 最初は r 番目の枠が r 番の箱を指している。 命令は五種類である。 - sort：順位表を作り直す。 重い箱を指す枠が前に来て、重さが同じなら番号の小さい箱が前に来る。 - add r v：順位表の r 番目の枠が指す箱の重さに v を足す。 順位表は作り直さない。 - swap i j：i 番の箱と j 番の箱の重さを入れ替える。 順位表の枠は引き続き同じ番号の箱を指す。 i と j は同じこともあり、そのときは何も変わらない。 - who r：順位表の r 番目の枠が指す箱の番号を一行に出力する。 - show：順位表の最初の枠から順に、枠が指す箱の重さ n 個を空白一つで区切って一行に出力する。 一行目に n と q、二行目に w_1 から w_n まで、続く q 行に命令が一つずつ与えられる。 重さは配列 int w[n] に置き、順位表はその要素を指すポインタ配列 int *rank[n] で作ってみよう。 sort では重さを動かさず、qsort（C++ は std::sort）でポインタだけを並べる。 重さが同じときは二つのポインタそのものを比べ、who はポインタの引き算 rank[r - 1] - w で番号を求めてみよう。 swap は二つの要素のアドレスを受け取る関数 void swap_weight(int *a, int *b) にしてみよう。
入力
1 ≤ n ≤ 1,000、1 ≤ q ≤ 2,000、1 ≤ r, i, j ≤ n。 重さと v は整数で、最初も add のあとも重さは常に -2,000,000,000 以上 2,000,000,000 以下（|v| もこの範囲内）。 show が出力する数は全部合わせて 15,000 個以下。 who か show は一回以上出てくる。
出力
who と show ごとに一行
例 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
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 2 言語の解答
この問題は C・C++ だけを受け付けます。 アドレスを値として持つポインタ、ポインタどうしの引き算で何枠離れているかを求めること、アドレスの大小比較はこの二つの言語にしかありません。 Python・JavaScript・TypeScript・Java・C#・Craykon では順位表に箱の番号（位置）を入れて w[rank[r]] でたどるのが同じことです（C# の本物のポインタは unsafe の中だけ）。 C の qsort は並べる枠のアドレスを const void * として比較関数に渡します。 枠に入っているのは int * なので、*(int *const *)pa で一回ほどくとポインタ、もう一回ほどくと（*a）重さが出てきます。 C++ の std::sort は比較関数に const int * を二つ直接渡します。 同じ配列の中を指す二つのポインタは < で比べられ（アドレスが小さければ番号も小さい）、引き算するとその間の枠の数になります（rank[r - 1] - w + 1 が番号）。 落とし穴は五つ：① 比較関数で *(const int *)pa のように一回しかほどかないと、重さではなくポインタの値の一部を比べてしまい、順番がめちゃくちゃになります。 ② return *b - *a; は 20億 - (-20億) のように差が int の範囲（約 21 億）を超えると符号が反転します。 大小を比べて -1・1 を返してください。 ③ 一時変数なしで *a ^= *b; *b ^= *a; *a ^= *b; と入れ替えると、a と b が同じ要素のとき（swap 3 3）重さが 0 になります。 二つのポインタが同じ場所を指しうること（エイリアス）をいつも考えましょう。 ④ 順位表にポインタではなく重さのコピーを置くと、add はコピーだけを変え、swap は順位表に表れません。 ⑤ 同じ重さを番号で分けずに C++ の std::stable_sort に任せると、元の番号順ではなく add・swap を経た今の順位表の順番が残ります。
C++main.cpp · 51 行
#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 行
#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;}