QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297612 | #6303. Inversion | yokeff | WA | 47ms | 35068kb | C++17 | 1.8kb | 2024-01-04 20:16:01 | 2024-01-04 20:16:01 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
//#define endl '\n'
using namespace std;
const int N=2e3+10;
const int mod=1e8;
typedef pair<int,int>PII;
int f[N][N];
int b[N],c[N],d[N];
int cnt=0;
int qr(int l,int r)
{
if(l>=r)return 0;
if(f[l][r]!=-1)return f[l][r];
cout<<"? "<<l<<" "<<r<<endl;
cnt++;
// assert(cnt<=60000);
cin>>f[l][r];
return f[l][r];
}
bool check(int l,int r)
{
return (qr(l,r)^qr(l+1,r)^qr(l,r-1)^qr(l+1,r-1));
}
void solve()
{
memset(f,-1,sizeof f);
int n;
cin>>n;
c[1]=1,b[1]=1;
for(int i=2;i<=n;i++)
{
// cout<<":: "<<endl;
// for(int j=1;j<i;j++)cout<<b[j]<<" ";cout<<endl;
int l=1,r=i-1;
while(l<r)
{
int mid=l+r>>1;
if(check(b[mid],i))r=mid;
else l=mid+1;
}
//4 if(l==2&&i==3)cout<<check(l,i)<<endl;
int pos=0;
if(check(b[l],i))
{
// cout<<"YE"<<endl;
for(int j=l;j<i;j++)c[j+1]=b[j];
c[l]=i,pos=l;
for(int j=1;j<l;j++)c[j]=b[j];
}
else
{
for(int j=1;j<=l;j++)c[j]=b[j];
c[i]=i,pos=i;
}
for(int j=1;j<=i;j++)d[c[j]]=j;
for(int j=i-1;j>=1;j--)f[j][i]=f[j+1][i]^(d[j]>d[i]);
for(int j=1;j<i;j++)f[j][i]^=f[j][i-1];
// for(int j=1;j<=i;j++)cout<<c[j]<<" ";cout<<endl;
for(int j=i;j>=1;j--)b[j]=c[j];
}
cout<<"! ";
vector<int>ans(n+1,0);
for(int i=1;i<=n;i++)ans[c[i]]=i;
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
cout<<endl;
}
signed main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 35044kb
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: 47ms
memory: 35068kb
input:
1993 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 4 ? 3 4 ? 2 5 ? 3 5 ? 2 4 ? 1 5 ? 2 6 ? 3 6 ? 3 5 ? 1 6 ? 1 5 ? 5 6 ? 1 7 ? 2 7 ? 1 6 ? 6 7 ? 5 7 ? 1 8 ? 2 8 ? 1 7 ? 5 8 ? 6 8 ? 5 7 ? 7 8 ? 8 9 ? 5 9 ? 6 9 ? 5 8 ? 7 9 ? 8 10 ? 9 10 ? 5 10 ? 6 10 ? 7 10 ? 6 11 ? 7 11 ? 9 11 ? 10 11 ? 8 11 ? 6 12 ? 7 12 ? 8 12 ? 11 12 ? 5 13 ?...
result:
wrong output format Unexpected end of file - int32 expected