QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#778876#6303. Inversionliuwei#TL 1ms3544kbC++141.5kb2024-11-24 16:40:192024-11-24 16:40:20

Judging History

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

  • [2024-11-24 16:40:20]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3544kb
  • [2024-11-24 16:40:19]
  • 提交

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;
int ask(int l,int r){
	if(l>=r)return 0;
	cout<<"?"<<" "<<l<<" "<<r<<endl;
	cout.flush();
	int x;
	cin>>x;
	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 len=r-l+1,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() {
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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


    while (t--) {
    	int n;
    	cin>>n;
    	solve(1,n);
    	cout<<"! ";
        rep(i,1,n){
        	q[p[i]]=i;
        	//cout<<p[i]<<endl;
		}
		rep(i,1,n)cout<<q[i]<<" ";
    }


    return 0;
}

詳細信息

Test #1:

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

input:

3
0
1
0
1
0

output:

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

result:

ok OK, guesses=5

Test #2:

score: -100
Time Limit Exceeded

input:

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

output:

? 1 2
? 1 2
? 2 3
? 3 4
? 2 4
? 3 4
? 2 3
? 2 3
? 1 2
? 2 3
? 1 2
? 2 3
? 1 2
? 1 2
? 2 3
? 3 4
? 2 4
? 3 4
? 2 3
? 2 3
? 4 5
? 3 4
? 3 5
? 4 5
? 3 4
? 2 5
? 3 5
? 2 4
? 3 4
? 1 5
? 2 5
? 1 4
? 2 4
? 4 6
? 5 6
? 4 5
? 3 6
? 4 6
? 3 5
? 4 5
? 2 4
? 3 4
? 2 3
? 2 3
? 2 6
? 3 6
? 2 5
? 3 5
? 1 6
? 2 6
...

result: