QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#428082 | #6303. Inversion | comeintocalm | WA | 70ms | 22276kb | C++20 | 1.5kb | 2024-06-01 17:20:35 | 2024-06-01 17:20:36 |
Judging History
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();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5908kb
input:
3 0 0 1
output:
? 1 2 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 70ms
memory: 22276kb
input:
1993 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 2 6 ? 3 6 ? 4 6 ? 5 6 ? 2 7 ? 3 7 ? 1 7 ? 5 7 ? 6 7 ? 2 8 ? 3 8 ? 5 8 ? 6 8 ? 7 8 ? 1 9 ? 2 9 ? 8 9 ? 7 9 ? 1 10 ? 2 10 ? 3 10 ? 4 10 ? 5 10 ? 6 10 ? 7 10 ? 1 11 ? 2 11 ? 4 11 ? 5 11 ? 3 11 ? 2 12 ? 3 12 ? 4 12 ? 5 12 ? 6 12 ? 7 12 ? 10 12 ? 11 12 ? ...
result:
wrong answer Wa.