看到这种题,应该考虑找一个特殊值,通过这个特殊值确定整个排列。
比如这题,找到 \(1\) 的位置,那么 \(a_i + 1 > a_j\) 等价于 \(a_i \ge a_j\),于是我们可以做一个比较次数为 \(n \log n\) 的排序。
找到 \(1\) 的位置也是容易的。注意到 \(1 + 1\) 不大于任何 \(\ge 2\) 的数,从左到右扫一遍,维护一个 \(p\),初始 \(p = 1\),如果 \(a_i + a_i \le a_p\),那么 \(p \gets i\)。这样能保证,扫完一边之后 \(a_p = 1\)。
code
// 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)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
inline int ask(int i, int j, int k) {
printf("? %d %d %d\n", i, j, k);
fflush(stdout);
char s[9];
scanf("%s", s);
return s[0] == 'Y';
}
const int maxn = 2020;
int n, a[maxn], b[maxn];
void solve() {
scanf("%d", &n);
if (n == 1) {
puts("! 1");
return;
}
int p = 1;
for (int i = 2; i <= n; ++i) {
if (!ask(i, i, p)) {
p = i;
}
}
for (int i = 1; i <= n; ++i) {
a[i] = i;
}
stable_sort(a + 1, a + n + 1, [&](int x, int y) {
return !ask(p, x, y);
});
for (int i = 1; i <= n; ++i) {
b[a[i]] = i;
}
printf("! ");
for (int i = 1; i <= n; ++i) {
printf("%d ", b[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest 154 gtatcoder regular contest 154 beginner atcoder contest 154 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest builder