QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#219572 | #6303. Inversion | ucup-team198 | WA | 67ms | 3776kb | C++23 | 1.5kb | 2023-10-19 16:21:30 | 2023-10-19 16:21:30 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ld eps=1e-8;
const int INF=0x3f3f3f3f,mod=998244353;
const ll INFF=0x3f3f3f3f3f3f3f3f;
#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif
const int N=2003;
int a[N];
int n;
int res[N];
int ask(int l,int r)
{
if(l>=r) return 0;
cout<<"? "<<l<<" "<<r<<endl;
int ans;
cin>>ans;
return ans;
}
vector<int> cdq_merge(int l,int r)
{
if(l==r)
{
return {l};
}
int mid=l+r>>1;
auto vl=cdq_merge(l,mid),vr=cdq_merge(mid+1,r);
vector<int> all;
int idl=0,idr=0;
while(idl<vl.size()&&idr<vr.size())
{
int L=vl[idl];
int R=vr[idr];
int ans=ask(L,R)^ask(L+1,R)^ask(L,R-1)^ask(L+1,R-1);
if(!ans)
{
all.push_back(vl[idl]);
idl++;
}
else
{
all.push_back(vr[idr]);
idr++;
}
}
while(idl<vl.size()) all.push_back(vl[idl++]);
while(idr<vr.size()) all.push_back(vr[idr++]);
return all;
}
int main()
{
scanf("%d",&n);
vector<int> all=cdq_merge(1,n);
for(int i=0;i<n;i++)
{
res[all[i]]=i+1;
}
cout<<"! ";
for(int i=1;i<=n;i++) cout<<res[i]<<" ";
cout<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3676kb
input:
3 0 0 1 0
output:
? 1 2 ? 1 3 ? 2 3 ? 1 2 ! 2 3 1
result:
ok OK, guesses=4
Test #2:
score: -100
Wrong Answer
time: 67ms
memory: 3776kb
input:
1993 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0...
output:
? 1 2 ? 3 4 ? 1 3 ? 2 3 ? 1 2 ? 2 3 ? 5 6 ? 7 8 ? 5 7 ? 6 7 ? 5 6 ? 5 8 ? 6 8 ? 5 7 ? 6 7 ? 6 8 ? 7 8 ? 6 7 ? 1 7 ? 2 7 ? 1 6 ? 2 6 ? 1 5 ? 2 5 ? 1 4 ? 2 4 ? 1 6 ? 2 6 ? 1 5 ? 2 5 ? 1 8 ? 2 8 ? 1 7 ? 2 7 ? 2 8 ? 3 8 ? 2 7 ? 3 7 ? 3 8 ? 4 8 ? 3 7 ? 4 7 ? 9 10 ? 11 12 ? 10 11 ? 9 11 ? 10 11 ? 9 10 ? 9...
result:
wrong output format Unexpected end of file - int32 expected