QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#778949#6303. Inversionliuwei#TL 1ms3804kbC++141.6kb2024-11-24 16:52:472024-11-24 16:52:48

Judging History

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

  • [2024-11-24 16:52:48]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3804kb
  • [2024-11-24 16:52:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a;i <= b;i++)
#define pre(i, a, b) for(int i = a;i >= b;i--)
#define pb push_back
const int N=2e3+5;
map<pair<int,int>,int>m;
int ask(int l,int r){
	if(l>=r)return 0;
	if(m.count({l,r}))return m[{l,r}];
	printf("? %d %d\n",l,r);//<<" "<<l<<" "<<r<<endl;
	fflush(stdout);
	int x;
	scanf("%d",&x); 
	m[{l,r}]=x;
	fflush(stdout);
	return x;
}
int get(int l,int r){//得到l和r的大小关系 
	int x=(ask(l,r)-ask(l+1,r)-ask(l,r-1)+ask(l+1,r-1)+4)%2;
//	cout<<l<<" @@"<<r<<" "<<x<<endl;
	return x;
}
int p[N];
void solve(int l,int r) {
	if(l==r){
		p[l]=l;
		return;
	}
    int mid=(l+r)/2;
    solve(1,mid);
    solve(mid+1,r);
    int x=mid,y=r;
    vector<int>w;
    //cout<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
    pre(i,r,l){
    	if(x>=l&&y>mid)
    	{
    		//cout<<x<<" "<<y<<"!"<<endl;
    		if(get(p[x],p[y])){
    			w.pb(p[x]);
    			//cout<<p[x]<<"!"<<p[y]<<" "<<x<<"!!"<<endl;
    			x--;
			}
			else 
			{
				w.pb(p[y]);
				//cout<<p[x]<<"!"<<p[y]<<" "<<x<<"!!"<<endl;
				y--;
			}
		}
		else if(x>=l){
			w.pb(p[x]);
			x--;
		}
		else{
			w.pb(p[y]);
			y--;
		}
	}
	rep(i,0,w.size()-1){
		p[r-i]=w[i];
	}
	//rep(i,l,r)cout<<p[i]<<" "<<l<<" "<<r<<endl;
    
}

int q[2005];
int main() {

    int t = 1;
    //cin>> t ;


    while (t--) {
    	int n;
    	scanf("%d",&n);
    	solve(1,n);
    	printf("! ");fflush(stdout);
        rep(i,1,n){
        	q[p[i]]=i;
        	//cout<<p[i]<<endl;
		}
		rep(i,1,n)printf("%d ",q[i]);
		printf("\n");
		fflush(stdout);
    }


    return 0;
}

詳細信息

Test #1:

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

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Time Limit Exceeded

input:

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

output:

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

result: