QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107635 | #6303. Inversion | __stick | WA | 0ms | 19256kb | C++20 | 1.9kb | 2023-05-22 10:26:38 | 2023-05-22 10:26:46 |
Judging History
answer
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
using namespace std;
template<typename T>
inline bool cmax(T&x,const T& y){return x<y?x=y,1:0;}
template<typename T>
inline bool cmin(T&x,const T& y){return y<x?x=y,1:0;}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef unsigned long long ull;
#define sz(x) (int(x.size()))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define em emplace
#define X first
#define Y second
const int mod=998244353;
inline void MOD(int&x){x-=mod,x+=x>>31&mod;}
inline void MOD(ll& x){x-=mod,x+=x>>63&mod;}
inline int add(int x,int y){MOD(x+=y);return x;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
template<typename ... A>inline int mul(const int& x,const A&... p){return 1ll*x*mul(p...)%mod;}
inline ll ksm(ll a,ll p=mod-2){ll ans=1;for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;return ans;}
typedef long double LD;
const int MAXN=2000+10;
int a[MAXN];
int res[MAXN][MAXN];
int p[MAXN];
inline int ask(int l,int r)
{
if(l==r)return 0;
if(~res[l][r])return res[l][r];
cout<<"? "<<l<<' '<<r<<endl;
int x;cin>>x;
return res[l][r]=x;
}
inline int cmp(int l,int r)
{
return ask(l,r)^ask(l+1,r)^p[l]^p[l+1];
}
int id[MAXN];
int main()
{
memset(res,-1,sizeof(res));
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(10);
int n;cin>>n;
if(n==1)
{
cout<<"! 1"<<endl;
return 0;
}
a[1]=1;
for(int i=2;i<=n;i++)
{
int l=1,r=i-1,ans=i;
while(l<=r)
{
int mid=(l+r)>>1;
if(cmp(mid,i))l=mid+1,ans=mid;
else r=mid-1;
}
for(int j=i;j>ans;j--)a[j]=a[j-1];
a[ans]=i;
for(int j=1;j<=i;j++)id[a[j]]=j;
int sum=0;
for(int j=i-1;j>=1;j--)
{
if(id[j]>id[i])sum^=1;
p[j]^=sum;
}
// cerr<<"!\n";
}
cout<<"! ";
for(int i=1;i<=n;i++)cout<<id[i]<<' ';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 19256kb
input:
3 0 0 1
output:
? 1 2 ? 1 3 ? 2 3 ! 1 3 2
result:
wrong answer Wa.