QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253618 | #6303. Inversion | SATSKY | WA | 54ms | 6140kb | C++20 | 1.7kb | 2023-11-17 10:14:32 | 2023-11-17 10:14:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;using ll=long long;const ll inf=3e18;const int M=1e9+7;
int o,o2,tc;
vector<int>res;
struct S
{
vector<int>arr,r2,rev;int n;
map<pair<int,int>,int>mp;
void ins(int id,int pos,int siz)
{
//cout<<siz<<':'<<pos<<'\n';
int pt=0;r2[pos]=id;
for(int i=1;i<=siz;i++)if(i!=pos)r2[i]=arr[++pt];
swap(arr,r2);
}
int query(int l,int r)
{
if(l>r)return 0;
if(mp.count({l,r}))return mp[{l,r}];
cout<<"? "<<l<<" "<<r<<endl;
int x=0;
cin>>x;
mp[{l,r}]=x;
//for(int i=l;i<r;i++)for(int j=i+1;j<=r;j++)x^=(res[i]>res[j]);
//cout<<l<<"#"<<r<<"#"<<x<<'\n';
return x;
}
bool chk(int a,int b)//a<b 0:r[a]<r[b] 1:r[a]>r[b]
{
bool sw=0;if(a>b)swap(a,b),sw=1;
bool x=query(a,b)^query(a+1,b)^query(a,b-1)^query(a+1,b-1);
//cout<<a<<"!!"<<b<<"!!"<<x<<'\n';
//if(bool(x)^(res[a]>res[b]))
//{
// cout<<a<<"!!"<<b<<"!!"<<x<<'\n';
//}
return x^sw;
}
void solve()
{
cin>>n;arr.resize(n+1),r2.resize(n+1);
//
//res.resize(n+1);for(int i=1;i<=n;i++)cin>>res[i];
//
arr[1]=1;
for(int i=2;i<=n;i++)
{
int p=i;
if(chk(arr[1],p)){ins(p,1,i);continue;}
if(!chk(arr[i-1],p)){ins(p,i,i);continue;}
int l=1,r=i;while(l<r-1)
{
int mid=(l+r)/2;chk(arr[mid],p)?r=mid:l=mid;
}
ins(p,r,i);
}
rev.resize(n+1);for(int i=1;i<=n;i++)rev[arr[i]]=i;
cout<<"!";for(int i=1;i<=n;i++)cout<<' '<<rev[i];cout<<endl;
}
};
int main()
{
//freopen("3.in","r",stdin);
//cout<<fixed<<setprecision(12);
//ios::sync_with_stdio(0);cin.tie(0);
int t=1;//cin>>t;o=(t>50);
//clock_t a=clock();
while(t--){S SS;SS.solve();}
//cout<<"Time:"<<double(clock()-a)<<'\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3448kb
input:
3 0 0 0 0 1
output:
? 1 2 ? 2 2 ? 1 1 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=5
Test #2:
score: -100
Wrong Answer
time: 54ms
memory: 6140kb
input:
1993 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1...
output:
? 1 2 ? 2 2 ? 1 1 ? 1 3 ? 2 3 ? 3 3 ? 1 4 ? 2 4 ? 3 4 ? 4 4 ? 1 5 ? 2 5 ? 5 6 ? 6 6 ? 5 5 ? 4 6 ? 4 5 ? 2 6 ? 3 6 ? 3 5 ? 1 6 ? 5 7 ? 6 7 ? 7 8 ? 8 8 ? 7 7 ? 4 8 ? 5 8 ? 4 7 ? 1 8 ? 2 8 ? 1 7 ? 2 7 ? 3 8 ? 3 7 ? 7 9 ? 8 9 ? 4 9 ? 5 9 ? 2 9 ? 3 9 ? 6 9 ? 6 8 ? 1 9 ? 7 10 ? 8 10 ? 4 10 ? 5 10 ? 9 10 ?...
result:
wrong output format Unexpected end of file - int32 expected