QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303553#6303. Inversionucup-team052#WA 1ms3752kbC++141.7kb2024-01-12 18:20:392024-01-12 18:20:39

Judging History

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

  • [2024-01-12 18:20:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3752kb
  • [2024-01-12 18:20:39]
  • 提交

answer

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=2005;
int n,a[N],suf[N];
int main(){
	rd(n);
	vector<int>order;
	rep(i,1,n){
		int l=0,r=SZ(order)-1,ret=-1;
		rep(i,0,SZ(order)-1)a[order[i]]=i;
		per(j,i-1,1){
			if(j<i-1)suf[j]=suf[j+1];
			else suf[j]=0;
			rep(k,j+1,i-1)suf[j]^=a[j]>a[k];
		}
		auto query=[&](int l,int r){
			if(r==i){
				printf("? %d %d\n",l,r);
				fflush(stdout);
				int x;
				scanf("%d",&x);
				return x;
			}else{
				assert(r==i-1);
				/*int x=0;
				rep(j,l,r)rep(k,j+1,r)x^=a[j]>a[k];
				assert(suf[l]==x);
				return suf[l];*/
			}
		};
		auto cmp=[&](int l,int r){
			return query(l,r)^query(l,r-1)^query(l+1,r)^query(l+1,r-1)^1;
		};
		while(l<=r){
			int mid=(l+r)>>1;
			if(cmp(order[mid],i)){
				ret=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		order.insert(order.begin()+(ret+1),i);
		DD(order);
	}
	rep(i,0,SZ(order)-1)a[order[i]]=i;
	printf("! ");
	rep(i,1,n)printf("%d ",a[i]+1);
	fflush(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3752kb

input:

3
0
1

output:

? 1 2
? 2 3
! 3 2 1 

result:

wrong answer Wa.