QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#299452 | #6303. Inversion | LittleXi# | WA | 132ms | 17456kb | C++17 | 1.4kb | 2024-01-06 21:09:12 | 2024-01-06 21:09:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int grid[2005][2005]={0};
int ask(int l,int r){
cout<<"? "<<l+1<<" "<<r+1<<endl;
int g = 0;
cin>>g;
return g;
}
int count(int l,int r){
int sm = 0;
for(int i =l;i<=r;i++)
sm += grid[i][l];
return sm%2;
}
void solve(){
int n ;
cin>>n;
if(n==1){
cout<<"! 1"<<endl;
return;
}
vector<int> p(1,0);
if(ask(0,1)){
p = {1,0};
}else p = {0,1};
for(int i = 2;i<n;i++){
int l = -1, r = p.size();
while(l+1!=r){
int m = l+r>>1;
vector<int> inv = {ask(p[m],i),count(p[m],i-1),ask(p[m]+1,i),count(p[m]+1,i-1)};
int comp = inv[0] - inv[1] -inv[2]+inv[3];
comp = (comp%2+2)%2;
if(comp) r = m;
else l =m;
}
p.insert(p.begin()+r,i);
vector<int> flg(n,0);
for(int j = r+1;j<p.size();j++){
flg[p[j]] = 1;
}
for(int j = i-1;j>=0;j--){
grid[i][j] = grid[i][j+1] + flg[j];
}
}
vector<int> ans(n,0);
for(int i=0;i<n;i++){
ans[p[i]] = i+1;
}
cout<<"! ";
for(int x:ans) cout<<x<<" ";
cout<<endl;
}
signed main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t = 1;
// cin>>t;
while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3740kb
input:
3 0 0 1
output:
? 1 2 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: 0
Accepted
time: 132ms
memory: 17456kb
input:
1993 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 0 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 3 3 ? 2 4 ? 3 4 ? 3 4 ? 4 4 ? 2 5 ? 3 5 ? 1 5 ? 2 5 ? 2 6 ? 3 6 ? 5 6 ? 6 6 ? 1 6 ? 2 6 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 1 8 ? 2 8 ? 3 8 ? 4 8 ? 2 8 ? 3 8 ? 1 9 ? 2 9 ? 8 9 ? 9 9 ? 2 9 ? 3 9 ? 9 10 ? 10 10 ? 5 10 ? 6 10 ? 7 10 ? 8 10 ? 1 11 ? 2 11 ? 8 11 ? 9 11 ? 9 11 ? 10 11 ? 11...
result:
ok OK, guesses=38179
Test #3:
score: -100
Wrong Answer
time: 97ms
memory: 16496kb
input:
1887 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0...
output:
? 1 2 ? 2 3 ? 3 3 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 3 4 ? 4 4 ? 1 5 ? 2 5 ? 3 5 ? 4 5 ? 4 5 ? 5 5 ? 3 6 ? 4 6 ? 5 6 ? 6 6 ? 4 6 ? 5 6 ? 3 7 ? 4 7 ? 6 7 ? 7 7 ? 5 7 ? 6 7 ? 7 8 ? 8 8 ? 6 8 ? 7 8 ? 4 8 ? 5 8 ? 7 9 ? 8 9 ? 6 9 ? 7 9 ? 8 9 ? 9 9 ? 4 9 ? 5 9 ? 5 10 ? 6 10 ? 1 10 ? 2 10 ? 2 10 ? 3 10 ? 7 11 ? 8 1...
result:
wrong answer Wa.