QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107635#6303. Inversion__stickWA 0ms19256kbC++201.9kb2023-05-22 10:26:382023-05-22 10:26:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-22 10:26:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:19256kb
  • [2023-05-22 10:26:38]
  • 提交

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.