QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333670 | #6303. Inversion | automac | WA | 0ms | 3540kb | C++20 | 1.6kb | 2024-02-20 11:58:39 | 2024-02-20 11:58:40 |
Judging History
answer
#include <bits/stdc++.h>
#define forn(i,n) for(int i=0; i < n; ++i)
#define for1(i,n) for(int i=1; i <= n; ++i)
#define fore(i,l,r) for(int i=l; i <= r; ++i)
#define pb push_back
#define el '\n'
#define sz(v) int(v.size())
#define d(v) cout << #v << " : " << v << el;
using namespace std;
typedef vector<int> vi;
const int N = 2001;
int cur, suf[N];
int ask(int l, int r){
if(l >= r) return 0;
if(r <= cur) return suf[l];
cout << "? " << l+1 << " " << r+1 << endl;
int inv; cin >> inv;
return inv;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
if(n == 1){
cout << "! " << 1 << endl;
return 0;
}
vi pos(n+1), val(n+1);
if(ask(0, 1)){
val[0] = 1; val[1] = 0;
pos[0] = 1; pos[1] = 0;
suf[0] = 1;
} else{
val[0] = pos[0] = 0;
val[1] = pos[1] = 1;
}
fore(i, 2, n-1){
int l = 0, r = i; // [l, r)
cur = i-1;
// d(i);
while(l+1 < r){
int m = (l + r) / 2;
int pm = pos[m];
int inv = ask(pm, i) ^ ask(pm+1, i) ^ ask(pm, i-1) ^ ask(pm+1, i-1);
// d(m); d(pm); d(inv); cout << el;
if(inv) l = m;
else r = m;
}
// d(l);
forn(j, i) if(val[j] >= l) ++val[j];
val[i] = l;
// forn(j, i+1) cout << val[j] << " ";
forn(j, i+1) pos[val[j]] = j;
int j = i-1, par = 0;
while(j >= 0){
par ^= val[j] > val[i];
suf[j] ^= par;
// d(suf[j]);
--j;
}
// cout << el << el;
}
cout << "! ";
forn(i, n) cout << val[i]+1 << " ";
cout << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3540kb
input:
3 0 1
output:
? 1 2 ? 2 3 ! 1 3 2
result:
wrong answer Wa.