QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243653#6303. InversionVengeful_Spirit#WA 55ms3420kbC++142.2kb2023-11-08 15:30:372023-11-08 15:30:38

Judging History

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

  • [2023-11-08 15:30:38]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:3420kb
  • [2023-11-08 15:30:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int A[10001];
/*
int query(int l,int r){
    assert(l<=r);
    if(l==r)return 0;
    cout<<"? "<<l<<" "<<r<<endl;
    int cnt=0;
    for(int i=l;i<=r;i++){
        for(int j=i+1;j<=r;j++){
            if(A[i]>A[j])cnt++;
        }
    }
    cout<<cnt%2<<endl;
    return cnt%2;
}
*/

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

int main(){
 //   srand(time(0));
    int n;
    cin>>n;
 //   for(int i=1;i<=n;i++)A[i]=i;
 //   random_shuffle(A+1,A+1+n);
   // for(int i=1;i<=n;i++)cout<<A[i]<<" ";cout<<endl;
    vector<int>b(n);
    for(int i=1;i<n;i++){
        b[i]=query(i,i+1);
    }
    vector<int>pos(n+1);
    pos[1]=1;
    for(int i=2;i<=n;i++){
        int l=1,r=i-1,res=0;
        auto myque=[&](int lim){
            int cnt=0;
            for(int i=1;i<=n;i++){
                if(i<lim&&pos[i]>pos[lim])cnt++;
            }
            return cnt&1;
        };
        auto check=[&](int mid){
            int x=query(pos[mid],i);
            int y=query(pos[mid]+1,i);
            int z=myque(mid);
          /*  if(i>pos[mid]+1)cout<<"check "<<i<<" "<<pos[mid]<<" "<<(x^y^b[pos[mid]]^1)<<endl;
            else cout<<"check "<<i<<" "<<pos[mid]<<" "<<(x^y^1)<<endl;
            if(i>pos[mid]+1)return x^y^b[pos[mid]]^1;
            else return x^y^1;
            */
     //      cout<<"check "<<i<<" "<<pos[mid]<<" "<<(x^y^z^1)<<endl;
           return x^y^z^1;
        };
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid)){
                res=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        for(int j=i;j>res;j--){
            pos[j]=pos[j-1];
        }
        pos[res+1]=i;
        vector<int>a(n+1);
        for(int i=1;i<=n;i++){
            a[pos[i]]=i;

        }
   /*     cout<<"! ";
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;*/
    }
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        a[pos[i]]=i;
    }
    cout<<"! ";
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3376kb

input:

3
0
1
0
0
1

output:

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

result:

ok OK, guesses=5

Test #2:

score: -100
Wrong Answer
time: 55ms
memory: 3420kb

input:

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

output:

? 1 2
? 2 3
? 3 4
? 4 5
? 5 6
? 6 7
? 7 8
? 8 9
? 9 10
? 10 11
? 11 12
? 12 13
? 13 14
? 14 15
? 15 16
? 16 17
? 17 18
? 18 19
? 19 20
? 20 21
? 21 22
? 22 23
? 23 24
? 24 25
? 25 26
? 26 27
? 27 28
? 28 29
? 29 30
? 30 31
? 31 32
? 32 33
? 33 34
? 34 35
? 35 36
? 36 37
? 37 38
? 38 39
? 39 40
? 40 ...

result:

wrong output format Unexpected end of file - int32 expected