QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303189 | #6303. Inversion | Szy | WA | 55ms | 3908kb | C++23 | 1.7kb | 2024-01-11 20:43:14 | 2024-01-11 20:43:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
int p[2003],a[2003],b[2003];
int ask(int i,int j)
{
if(i==j)return 0;
cout<<"? "<<i<<" "<<j<<endl;
int get;
scanf("%d",&get);
return get;
}
int mx(int l,int r)
{
int f=0;
if(l>r)
{
f=1;
swap(l,r);
}
int v;
if(l+1==r)v=ask(l,r);
else v=((ask(l,r)-ask(l,r-1)-ask(l+1,r)+ask(l+1,r-1))%2+2)%2;
return v^f;//1:pl>pr 0:pl<pr
}
/*int mx_id(int l,int r)
{
int id=l;
for(int i=l+1;i<=r;++i)
{
if(mx(id,i)==0)id=i;
}
return id;
}*/
void merge(int l,int r,int mid)
{
for(int i=l;i<=r;++i)
{
b[i]=a[i];
}
int z1=l,z2=mid+1,z=l;
while(z1<=mid&&z2<=r)
{
if(mx(b[z1],b[z2])==0)
{
a[z]=b[z1];
++z;
++z1;
}
else
{
a[z]=b[z2];
++z;
++z2;
}
}
while(z1<=mid)
{
a[z]=b[z1];
++z;
++z1;
}
while(z2<=r)
{
a[z]=b[z2];
++z;
++z2;
}
}
void st(int l,int r)
{
if(l>=r)return;
int mid=(l+r)/2;
st(l,mid);
st(mid+1,r);
merge(l,r,mid);
}
void sol()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
a[i]=i;
}
st(1,n);
for(int i=1;i<=n;++i)
{
p[a[i]]=i;
}
cout<<"!";
for(int i=1;i<=n;++i)
{
printf(" %d",p[i]);
}
cout<<endl;
}
int main()
{
int TT=1;
//scanf("%d", &TT);
while (TT--) sol();
return 0;
}
/*
4
2
1 2
4
1 2
2 3
3 4
4
1 2
2 3
2 4
5
1 2
3 5
2 3
3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3900kb
input:
3 0 0 0 1
output:
? 1 2 ? 1 3 ? 1 2 ? 2 3 ! 2 3 1
result:
ok OK, guesses=4
Test #2:
score: -100
Wrong Answer
time: 55ms
memory: 3908kb
input:
1993 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0...
output:
? 1 2 ? 3 4 ? 1 3 ? 1 2 ? 2 3 ? 2 3 ? 5 6 ? 7 8 ? 5 7 ? 5 6 ? 6 7 ? 5 8 ? 5 7 ? 6 8 ? 6 7 ? 6 8 ? 6 7 ? 7 8 ? 1 7 ? 1 6 ? 2 7 ? 2 6 ? 1 5 ? 1 4 ? 2 5 ? 2 4 ? 1 6 ? 1 5 ? 2 6 ? 2 5 ? 1 8 ? 1 7 ? 2 8 ? 2 7 ? 2 8 ? 2 7 ? 3 8 ? 3 7 ? 3 8 ? 3 7 ? 4 8 ? 4 7 ? 9 10 ? 11 12 ? 10 11 ? 9 11 ? 9 10 ? 10 11 ? 9...
result:
wrong output format Unexpected end of file - int32 expected