[Codeforces] Codeforces Round #669 (Div. 2) C. Chocolate Bunny
問題
方針
剰余の単調増加性を利用して解きます。自然数 \( x, y \) を用いて \( x \bmod y \) と \( y \bmod x \) を考えます。また、\( x \neq y \) とします。
\[ y \bmod x < x \bmod y \]
を満たすとき、\( x < y \) であることが分かります。つまり、\( x < y \) であるとき、
\[ x = x \bmod y\]
を満たします。したがって、"? i j" と “? j i"というクエリを投げた時、\( p_i \) または \( p_j \) のどちらかの値が判明します。
したがって、\( p_i \bmod p_j < p_j \bmod p_i \) を満たす \( i \) を更新し、全探索します。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n; cin >> n; if (n == 1) { cout <<"! 1" << "\n"; return 0; } int ans[n]{}; int id = 1; for (int i = 1; i + 1 <= n; i++) { int a1, a2; cout << "? " << id << " " << i + 1 << "\n"; cin >> a1; cout << "? " << i + 1 << " " << id << "\n"; cin >> a2; if (a1 < a2) { ans[i] = a2; } else { ans[id - 1] = a1; id = i + 1; } } ans[id - 1] = n; cout << "! "; for (int i = 0; i < n; i++) { if (i == n - 1) { cout << ans[i] << "\n"; } else { cout << ans[i] << " "; } } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません