QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#238235 | #6303. Inversion | REN_REN# | WA | 70ms | 7424kb | C++14 | 1.9kb | 2023-11-04 16:10:10 | 2023-11-04 16:10:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
map<pair<int,int>, int> v;
bool check(int l,int r) {
auto h = v.find({l,r});
if(h != v.end()) {
return v[{l,r}];
}
else {
cout << "? " << l << ' ' << r << endl;
int hh;
cin >> hh;
v[{l,r}] = hh;
return hh;
}
}
void solve(){
int n;
cin >> n;
int l, r;
vector<int> aa;
aa.push_back(1);
vector<int> po(n+1);
po[1] = 1;
for(int i = 2; i <= n; i ++) {
int numl = 0, numr = i;
int por = i;
int h, h1, h2, h3, h4;
while(numr - numl > 1) {
int mid = numl + numr >> 1;
int pol = po[mid];
if(pol == por - 1) {
// cout << "? " << pol << ' ' << por << endl;
// cin >> h;
h = check(pol, por);
// cout << h << '\n';
if(h) {
numr = mid;
}
else numl = mid;
}
else {
int ans = 0;
// cout << "? " << pol << ' ' << por << endl;
// cin >> h2;
h2 = check(pol, por);
// cout << "? " << pol << ' ' << por - 1 << endl;
// cin >> h4;
h4 = check(pol, por - 1);
if(por - pol == 2) {
// cout << "? " << pol + 1 << ' ' << por << endl;
// cin >> h1;
h1 = check(pol + 1, por);
ans ^= h1;
}
else {
// cout << "? " << pol + 1 << ' ' << por << endl;
// cin >> h1;
h1 = check(pol + 1, por);
// cout << "? " << pol + 1 << ' ' << por - 1 << endl;
// cin >> h3;
h3 = check(pol + 1, por - 1);
ans ^= h1 ^ h3;
}
// cout << ans << ' ' << h2 << ' ' << h4 << '\n';
if(ans ^ h2 ^ h4) {
numr = mid;
}
else numl = mid;
}
}
for(auto &i : aa) {
if(i >= numr) {
i ++;
}
}
aa.push_back(numr);
for(int i = 0; i < aa.size(); i ++) {
po[aa[i]] = i + 1;
}
}
cout << "! ";
for(auto i : aa) {
cout << i << ' ';
}
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
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: 7424kb
input:
1993 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 1 4 ? 2 6 ? 3 6 ? 5 6 ? 1 6 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 1 8 ? 2 8 ? 3 8 ? 3 7 ? 4 8 ? 4 7 ? 1 9 ? 2 9 ? 8 9 ? 3 9 ? 9 10 ? 5 10 ? 5 9 ? 6 10 ? 6 9 ? 7 10 ? 7 9 ? 8 10 ? 1 11 ? 1 10 ? 2 11 ? 2 10 ? 8 11 ? 9 11 ? 10 11 ? 11 12 ? 8 12 ? 9 12 ? 10 12 ? 2 1...
result:
wrong output format Unexpected end of file - int32 expected