QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303788 | #6303. Inversion | mc020207 | WA | 37ms | 3616kb | C++17 | 1.1kb | 2024-01-12 23:56:57 | 2024-01-12 23:56:58 |
Judging History
answer
#include<bits/stdc++.h>
#define MAXN 500010
#define INF 1000000010
#define MOD 998244353
#define LL long long
#define LLL __int128_t
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int a[MAXN],p[MAXN];
int ans[MAXN];
int nowr;
int ask(int x,int y){
if (x==y) return 0;
if (y<nowr) return ans[x];
cout<<"? "<<x<<" "<<y<<endl;
int ans;cin>>ans;
return ans;
}
bool check(int x,int y){ // a[x]>a[y]
assert(x<y);
if (x==y-1) return ask(x,y);
return (ask(x,y)^ask(x+1,y)^ask(x,y-1)^ask(x+1,y-1));
}
void Main(){
int n;cin>>n;
a[1]=1,p[1]=1,ans[1]=0;
For(i,2,n){
nowr=i;
int l=1,r=i-1,answer=0;
while (l<=r){
int mid=l+r>>1;
if (check(p[mid],i)){
r=mid-1;
}else{
answer=mid;
l=mid+1;
}
}
For(j,1,i){
if (a[j]>answer){
a[j]++;
p[a[j]]=j;
ans[j]^=1;
}
}
a[i]=answer+1;
p[answer+1]=i;
}
cout<<"!";
For(i,1,n) cout<<" "<<a[i];
cout<<endl;
}
int main(){
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;/* cin>>T; */
while (T--) Main();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
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: 37ms
memory: 3616kb
input:
1993 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 2 4 ? 3 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 2 5 ? 2 6 ? 3 6 ? 3 6 ? 4 6 ? 4 6 ? 5 6 ? 2 7 ? 3 7 ? 5 7 ? 6 7 ? 2 8 ? 3 8 ? 5 8 ? 6 8 ? 7 8 ? 1 9 ? 2 9 ? 8 9 ? 7 9 ? 8 9 ? 1 10 ? 2 10 ? 3 10 ? 4 10 ? 2 10 ? 3 10 ? 1 11 ? 2 11 ? 9 11 ? 10 11 ? 8 11 ? 9 11 ? 5 11 ? 6 11 ? 1 12 ? 2 12 ?...
result:
wrong answer Wa.