QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303599 | #6303. Inversion | xuyufeiya | WA | 1ms | 3968kb | C++20 | 2.0kb | 2024-01-12 19:53:50 | 2024-01-12 19:53:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
auto query = [](auto self, int x, int y) -> int {
if(x > y) return -self(self, y, x);
if(x == 0) return -1;
int ret = 0, a;
if(x + 1 == y) {
printf("? %d %d\n", x, y);
fflush(stdout);
cin >> a;
ret ^= a;
} else {
printf("? %d %d\n", x + 1, y);
fflush(stdout);
cin >> a;
ret ^= a;
printf("? %d %d\n", x, y - 1);
fflush(stdout);
cin >> a;
ret ^= a;
printf("? %d %d\n", x, y);
fflush(stdout);
cin >> a;
ret ^= a;
if(x + 1 != y - 1) {
printf("? %d %d\n", x + 1, y - 1);
fflush(stdout);
cin >> a;
ret ^= a;
}
}
ret = (ret? 1: -1);
//printf(":%d %d %d\n", x, y, ret);
return ret;
};
// 4 2 1 3
vector<int> pos;
pos.push_back(0);
for(int i = 1; i <= n; i++) {
int lh = 0, rh = pos.size() - 1, ans = -1;
while(lh <= rh) {
int mid = (lh + rh) / 2, tmp;
//printf("--- %u %d %d %d\n", pos.size(), lh, rh, mid);
if((tmp = query(query, i, pos[mid])) > 0) {
ans = mid;
lh = mid + 1;
} else {
rh = mid - 1;
}
//printf("-- %d %d %d\n", i, pos[mid], tmp);
}
//printf(":::::%d\n", ans);
pos.insert(pos.begin() + ans + 1, i);
//printf("::");
//for(int i = 1; i < pos.size(); i++) printf("%d ", pos[i]);
//printf("\n");
}
vector<int> out(n + 1);
for(int i = 1; i <= n; i++) out[pos[i]] = i;
for(int i = 1; i <= n; i++) printf("%d%c", out[i], i == n? '\n': ' ');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3968kb
input:
3 0 1 0 0
output:
? 1 2 ? 2 3 ? 1 2 ? 1 3 2 3 1
result:
wrong output format Unexpected end of file - int32 expected