[Codeforces] Codeforces Round #669 (Div. 2) C. Chocolate Bunny

2020年12月13日

問題

方針

剰余の単調増加性を利用して解きます。自然数 \( 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;
}