CF 1407C Chocolate Bunny

题目描述

https://codeforces.com/contest/1407/problem/C

Solution

首先有一个比较显然的性质

$(a\bmod b>b\bmod a\Longleftrightarrow a<b)$

那么我们从 $1$ 干到 $n$，最后留下的数一定是 $n$

中间那些数在做两次询问的时候就已经求出来了，总共只需要用 $2n-2$ 询问

#include <iostream>
#include <cstdio>
#define maxn 10010
using namespace std;

int n, a[maxn], p;

int ans[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; p = 1;
    for (int i = 2; i <= n; ++i) {
        int x, y; 
        cout << "? " << p << " " << i << endl;
        cin >> x;
        cout << "? " << i << " " << p << endl;
        cin >> y;
        if (x > y) ans[p] = x, p = i;
        else ans[i] = y; 
    } ans[p] = n;
    cout << "! "; for (int i = 1; i <= n; ++i) cout << ans[i] << " "; cout << "\n";
    return 0;
}