QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#257573#6303. InversionCryingWA 50ms17348kbC++171.2kb2023-11-19 10:24:592023-11-19 10:24:59

Judging History

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

  • [2023-11-19 10:24:59]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:17348kb
  • [2023-11-19 10:24:59]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 2010;

int n,p[MAXN],f[MAXN][MAXN];

int query(int l,int r){
	if(l>=r)return 0;
	cout<<"? "<<l<<" "<<r<<endl;
	int ret; cin>>ret;
	return ret;
}

int chk(int j,int i){ //check whether p[j] < p[i]
	int r = f[j+1][i-1] ^ f[j][i-1] ^ query(j+1,i) ^ query(j,i);
	return !r;
}

int main(){
	cin>>n;
	p[1] = 1;
	//

	rep(i,2,n){
		int L = 1,R = i-1,ret = 0;
		while(L<=R){
			int mid = (L+R)>>1,j = -1;
			rep(k,1,i-1)if(p[k]==mid){j=k;break;} assert(j!=-1);
			if(chk(j,i)){
				ret = mid;L = mid+1;
			}else{
				R = mid-1;
			}
		}
		p[i] = ret+1;
		rep(j,1,i-1)if(p[j] > ret)p[j]++;
		
		int sum = 0;
		per(j,i-1,1){
			sum += (p[j]>p[i]);
			f[j][i] = f[j][i-1]+sum;
		}
	}

	//
	cout<<"! "; rep(i,1,n)cout<<p[i]<<" ";cout<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 50ms
memory: 17348kb

input:

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

output:

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

result:

wrong answer Wa.