题解 ARC154D【A + B > C ?】

rui_er · 2023-01-24 20:25:25 · 题解

显然 1+1>x 对任意大于 1 的正整数 x 都不成立。利用这一点，我们可以在 n-1 次询问内问出 1 的位置。具体地，首先假设 p_1 为 1，记我们假设的为 1 位置为 k。依次枚举 2\sim n 的每个数 x，问 p_k+p_k>p_x 是否成立。若成立，意味着 p_k>1，令 k\gets x 然后继续循环；若不成立，意味着 p_x>1，继续循环。循环结束后，p_k=1 一定成立。

注意到 p_i+1>p_j\iff p_i\ge p_j，我们有了比较操作，只需对 p 进行排序即可。可以手写归并排序，但更方便的方法是写一个比较函数传进 stable_sort 里面。注意这里用 sort 可能会被卡，原因是 sort 递归到 n 小后就会使用插入排序，导致比较次数超限（次数限制比较紧）。

// Problem: D - A + B > C ?
// Contest: AtCoder - AtCoder Regular Contest 154
// URL: https://atcoder.jp/contests/arc154/tasks/arc154_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e3+5;

int n, a[N], p[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int ask(int x, int y, int z) {
    printf("? %d %d %d\n", x, y, z);
    fflush(stdout);
    char s[4];
    scanf("%s", s);
    return s[0] == 'Y';
}
void give(int* p, int n) {
    printf("! ");
    rep(i, 1, n) printf("%d%c", p[i], " \n"[i==n]);
    fflush(stdout);
}

int main() {
    scanf("%d", &n);
    int pos1 = 1;
    rep(i, 2, n) if(ask(pos1, pos1, i)) pos1 = i;
    rep(i, 1, n) a[i] = i;
    stable_sort(a+1, a+1+n, [=](int i, int j) {
        return !ask(i, pos1, j);
    });
    rep(i, 1, n) p[a[i]] = i;
    give(p, n);
    // system("pause");
    return 0;
}