QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#428080 | #6303. Inversion | comeintocalm | TL | 0ms | 0kb | C++20 | 1.5kb | 2024-06-01 17:20:16 | 2024-06-01 17:20:17 |
answer
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N = 2e3+7;
int Q[N][N];
bool vis[N][N];
int query(int l, int r) {
if(l == r) return 0;
if(vis[l][r]) return Q[l][r];
printf("? %d %d\n", l, r);
//cout.flush();
int x;
scanf("%d", &x);
vis[l][r] = 1;
Q[l][r] = x;
return x;
}
int pos[N], tmp[N], n;
/// pos[mid] the position of number ranked mid
void mov(int l, int i) {
for(int x = 1; x < l; x++)
tmp[x] = pos[x];
for(int x = l; x < i; x++)
tmp[x + 1] = pos[x];
tmp[l] = i;
for(int x = 1; x <= i; x++)
pos[x] = tmp[x];
}
int ask(int mid, int x) {
int cnt = 0;
for(int i = mid + 1; i < x; i++) {
if(pos[i] < pos[mid]) cnt++;
}
return cnt & 1;
}
int check(int mid, int x) {
int val = query(pos[mid], x) ^ query(pos[mid] + 1, x) ^ ask(mid, x);
return val & 1;
}
void solve() {
pos[1] = 1;
for(int i = 2; i <= n; i++) {
int l = 1, r = i - 1, tar = l;
while(l < r) {
int mid = (l + r) / 2;
if(check(mid, i)) tar = mid, r = mid;
else l = mid + 1;
}
if(l == r) {
if(!check(r, i)) {
pos[i] = i;
} else mov(tar, i);
} else mov(tar, i);
}
for(int i = 1; i <= n; i++) tmp[pos[i]] = i;
printf("! ");
for(int i = 1; i <= n; i++) printf("%d ", tmp[i]);
printf("\n");
}
int main() {
scanf("%d", &n);
if(n == 1) {
printf("1\n");
return 0;
}
solve();
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3