QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303788#6303. Inversionmc020207WA 37ms3616kbC++171.1kb2024-01-12 23:56:572024-01-12 23:56:58

Judging History

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

  • [2024-01-12 23:56:58]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:3616kb
  • [2024-01-12 23:56:57]
  • 提交

answer

#include<bits/stdc++.h>
#define MAXN 500010
#define INF 1000000010
#define MOD 998244353
#define LL long long
#define LLL __int128_t
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int a[MAXN],p[MAXN];
int ans[MAXN];
int nowr;
int ask(int x,int y){
	if (x==y) return 0;
	if (y<nowr) return ans[x];
	cout<<"? "<<x<<" "<<y<<endl;
	int ans;cin>>ans;
	return ans;
}
bool check(int x,int y){ // a[x]>a[y]
	assert(x<y);
	if (x==y-1) return ask(x,y);
	return (ask(x,y)^ask(x+1,y)^ask(x,y-1)^ask(x+1,y-1));
}
void Main(){
	int n;cin>>n;
	a[1]=1,p[1]=1,ans[1]=0;
	For(i,2,n){
		nowr=i;
		int l=1,r=i-1,answer=0;
		while (l<=r){
			int mid=l+r>>1;
			if (check(p[mid],i)){
				r=mid-1;
			}else{
				answer=mid;
				l=mid+1;
			}
		}
		For(j,1,i){
			if (a[j]>answer){
				a[j]++;
				p[a[j]]=j;
				ans[j]^=1;
			}
		}
		a[i]=answer+1;
		p[answer+1]=i;
	}
	cout<<"!";
	For(i,1,n) cout<<" "<<a[i];
	cout<<endl;
}
int main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;/* cin>>T; */
	while (T--) Main();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 37ms
memory: 3616kb

input:

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

output:

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

result:

wrong answer Wa.