QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#353602 | #6303. Inversion | crsfaa# | WA | 71ms | 6712kb | C++14 | 2.4kb | 2024-03-14 12:02:30 | 2024-03-14 12:02:30 |
Judging History
answer
#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int p[2005];
int p0[2005];
int cnt;
map<pair<int,int>,int> mp;
bool ask(int l,int r)
{
if(l>=r) return 0;
if(mp.count({l,r})) return mp[{l,r}];
printf("? %d %d\n",l,r);
cnt++;
fflush(stdout);
// int c=0;
// for(int i=l;i<=r;i++)
// for(int j=i+1;j<=r;j++)
// c^=p0[i]>p0[j];
// cout<<"q "<<c<<endl;
int c;
cin>>c;
return mp[{l,r}]=c;
}
bool get(int l,int r)
{
bool fl=0;
if(l>r) swap(l,r),fl=1;
return ask(l,r)^ask(l+1,r)^ask(l,r-1)^ask(l+1,r-1)^fl;
}
bool cmp(int x,int y)
{
return p[x]<p[y];
}
int qwq[2005];
void solve(int l,int r)
{
if(l>=r)
{
p[l]=1;
return;
}
int mid=l+r>>1,i,j,cnt=0;
solve(l,mid),solve(mid+1,r);
deque<int> a,b;
for(i=l;i<=mid;i++)
a.push_back(i);
for(;i<=r;i++)
b.push_back(i);
sort(a.begin(),a.end(),cmp);
sort(b.begin(),b.end(),cmp);
if(rand()%2)
{
qwq[mid-1]=0;
for(i=mid;i<=r;i++)
qwq[i]=ask(l,i);
for(i=r;i>mid;i--)
qwq[i]^=qwq[i-1];
for(i=mid+1;i<=r;i++)
{
// cout<<l<<' '<<r<<' '<<i<<':'<<qwq[i]<<endl;
for(j=mid+1;j<i;j++)
qwq[i]^=(p[j]>p[i]);
qwq[i]^=(mid-l+1)%2;
}
int cnt2=0;
while(a.size()&&b.size())
if(cnt2==qwq[b.front()]&&get(a.front(),b.front()))
p[b.front()]=++cnt,b.pop_front();
else
p[a.front()]=++cnt,a.pop_front(),cnt2^=1;
}
else
{
qwq[mid+2]=0;
for(i=mid+1;i>=l;i--)
qwq[i]=ask(i,r);
for(i=l;i<=mid;i++)
qwq[i]^=qwq[i+1];
for(i=mid;i>=l;i--)
{
for(j=i+1;j<=mid;j++)
qwq[i]^=(p[i]>p[j]);
}
int cnt2=0;
while(a.size()&&b.size())
if(cnt2==qwq[a.front()]&&!get(a.front(),b.front()))
p[a.front()]=++cnt,a.pop_front();
else
p[b.front()]=++cnt,b.pop_front(),cnt2^=1;
}
for(auto x:a)
p[x]=++cnt;
for(auto x:b)
p[x]=++cnt;
// cout<<l<<' '<<r<<':';
// for(int i=l;i<=r;i++)
// cout<<p[i]<<' ';
// puts("");
}
/*
10
1 10 9 3 4 6 7 8 2 5
*/
int main()
{
srand(114514);
int n=read(),i;
for(i=1;i<=n;i++)
p0[i]=i;
random_shuffle(p0+1,p0+1+n);
// for(i=1;i<=n;i++)
// cout<<p0[i]<<' ';
// puts("");
solve(1,n);
printf("! ");
for(i=1;i<=n;i++)
printf("%d ",p[i]);
puts("");
fflush(stdout);
// cout<<cnt;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3772kb
input:
3 0 1 0
output:
? 1 2 ? 2 3 ? 1 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 71ms
memory: 6712kb
input:
1993 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 1 1...
output:
? 1 2 ? 3 4 ? 2 4 ? 1 4 ? 1 3 ? 2 3 ? 5 6 ? 7 8 ? 6 8 ? 5 8 ? 5 7 ? 6 7 ? 4 8 ? 3 8 ? 2 8 ? 1 8 ? 1 5 ? 2 5 ? 1 7 ? 2 7 ? 3 7 ? 9 10 ? 11 12 ? 10 12 ? 9 12 ? 10 11 ? 9 11 ? 13 14 ? 15 16 ? 14 16 ? 13 16 ? 14 15 ? 13 15 ? 9 13 ? 9 14 ? 9 15 ? 9 16 ? 11 14 ? 12 14 ? 11 13 ? 12 13 ? 10 15 ? 10 14 ? 10 ...
result:
wrong output format Unexpected end of file - int32 expected