QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303718 | #6303. Inversion | Aicu | WA | 83ms | 19388kb | C++20 | 1.8kb | 2024-01-12 22:09:27 | 2024-01-12 22:09:27 |
Judging History
answer
/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N=2e3+10;
map<pii,int>mp;
int ask(int l,int r){
if(l==r) return 0;
if(mp.count({l,r})!=0) return mp[{l,r}];
cout<<'?'<<' '<<l+1<<' '<<r+1<<'\n';
cout.flush();
int x;cin>>x;
mp[{l,r}]=x;
return x;
}
int f[N][N]; //inversions of [l,r]
int ask2(int l,int r){
int x=ask(l,r);
int y=ask(l+1,r);
int a=f[l][r-1];
int b=f[l+1][r-1];
int d=x^y^a^b;
return d;
}
void solve(){
int n;cin>>n;
vector<int>a(n),pos(n);
a[0]=pos[0]=0;
int p=1;
while(p<n){
auto check=[&](int m) -> bool {
m=pos[m];
int d=ask2(m,p);
return d;
};
int l=-1,r=p;
while(l+1<r){
int m=l+r>>1;
if(check(m)) r=m;
else l=m;
}
for(int i=p-1;i>=r;i--){
int cp=pos[i];
a[cp]++;
pos[a[cp]]=cp;
}
a[p]=r;
pos[r]=p;
int inv=0;
for(int i=p-1;i>=0;i--){
if(a[i]>a[p]) inv++;
f[i][p]=f[i][p-1]+inv;
}
p++;
}
cout<<'!'<<' ';
for(int i=0;i<n;i++){
cout<<a[i]+1<<' ';
}
cout<<'\n';
}
signed main()
{
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
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: 83ms
memory: 19388kb
input:
1993 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 2 6 ? 3 6 ? 5 6 ? 1 6 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 1 8 ? 2 8 ? 5 8 ? 6 8 ? 7 8 ? 6 9 ? 7 9 ? 8 9 ? 6 10 ? 7 10 ? 9 10 ? 8 10 ? 5 11 ? 6 11 ? 10 11 ? 9 11 ? 5 12 ? 6 12 ? 11 12 ? 9 12 ? 10 12 ? 8 13 ? 9 13 ? 11 13 ? 12 13 ? 10 13 ? 8 14 ? 9 14 ? 11 14 ? ...
result:
wrong answer Wa.