QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180023 | #6303. Inversion | ucup-team045# | WA | 42ms | 19332kb | C++20 | 1.7kb | 2023-09-15 14:41:39 | 2023-09-15 14:41:40 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<random>
using namespace std;
using LL = long long;
int dp[2005][2005];
int main(){
// #ifdef LOCAL
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
// #endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
memset(dp, -1, sizeof dp);
auto ask = [&](int l, int r){
if (l >= r) return 0;
if (dp[l][r] != -1) return dp[l][r];
cout << "? " << l + 1 << ' ' << r + 1 << endl;
int t;
cin >> t;
return dp[l][r] = t;
};
vector<int> id(n);
for(int i = 0; i < n; i++) id[i] = i;
mt19937 rnd(random_device{}());
shuffle(id.begin(), id.end(), rnd);
vector<int> c{id[0]};
for(int i = 1; i < id.size(); i++){
auto check = [&](int a, int b){
if (a < b){
int c1 = ask(a, b);
int c2 = ask(a + 1, b);
int c3 = ask(a, b - 1);
int c4 = ask(a + 1, b - 1);
return c1 ^ c2 ^ c3 ^ c4;
}
swap(a, b);
int c1 = ask(a, b);
int c2 = ask(a + 1, b);
int c3 = ask(a, b - 1);
int c4 = ask(a + 1, b - 1);
return c1 ^ c2 ^ c3 ^ c4 ^ 1;
};
int l = 0, r = i;
while(l < r){
int mid = (l + r) / 2;
if (check(c[mid], id[i])) r = mid;
else l = mid + 1;
}
c.insert(c.begin() + r, id[i]);
}
vector<int> ans(n);
for(int i = 0; i < c.size(); i++)
ans[c[i]] = i;
cout << "! ";
for(auto x : ans) cout << x + 1 << ' ';
cout << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 19332kb
input:
3 0 1 0
output:
? 1 3 ? 2 3 ? 1 2 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 42ms
memory: 19232kb
input:
1993 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 0 0...
output:
? 813 1635 ? 814 1635 ? 813 1634 ? 814 1634 ? 837 1635 ? 838 1635 ? 837 1634 ? 838 1634 ? 813 837 ? 814 837 ? 813 836 ? 814 836 ? 813 1678 ? 814 1678 ? 813 1677 ? 814 1677 ? 837 1678 ? 838 1678 ? 837 1677 ? 838 1677 ? 49 813 ? 50 813 ? 49 812 ? 50 812 ? 49 1635 ? 50 1635 ? 49 1634 ? 50 1634 ? 813 81...
result:
wrong output format Unexpected end of file - int32 expected