题解 ARC154D【A + B > C ?】

显然 \(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;
}