QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#303546#6303. Inversionucup-team052#WA 181ms3800kbC++141.6kb2024-01-12 18:10:272024-01-12 18:10:28

Judging History

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

  • [2024-01-12 18:10:28]
  • 评测
  • 测评结果:WA
  • 用时:181ms
  • 内存:3800kb
  • [2024-01-12 18:10:27]
  • 提交

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];
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;
		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{
				int x=0;
				rep(i,l,r)rep(j,l+1,r){
					x+=a[i]>a[j];
				}
				return x;
			}
		};
		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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

input:

3
0
0
0
1

output:

? 1 2
? 2 2
? 1 3
? 2 3
! 2 3 1 

result:

ok OK, guesses=4

Test #2:

score: -100
Wrong Answer
time: 181ms
memory: 3800kb

input:

1993
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
1
1
0
0
1
1
0
0
0
1
0
0
1
0
1
1
0
1
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
1
0
0
0
1
1
0
1
0
0
0
0
1
0
1
1
1
1
1
1
1
0
0
0
1
0
1
1
0
1
0
0
0
1
0
0
1
0
1
1
0
0
1
1
0
0
0
1
0...

output:

? 1 2
? 2 2
? 1 3
? 2 3
? 2 3
? 3 3
? 2 4
? 3 4
? 3 4
? 4 4
? 2 5
? 3 5
? 3 5
? 4 5
? 5 6
? 6 6
? 3 6
? 4 6
? 4 6
? 5 6
? 5 7
? 6 7
? 1 7
? 2 7
? 2 7
? 3 7
? 5 8
? 6 8
? 6 8
? 7 8
? 4 8
? 5 8
? 5 9
? 6 9
? 6 9
? 7 9
? 4 9
? 5 9
? 8 9
? 9 9
? 3 10
? 4 10
? 4 10
? 5 10
? 9 10
? 10 10
? 3 11
? 4 11
? 1...

result:

wrong answer Wa.