QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243618#6303. InversionVengeful_Spirit#WA 56ms3404kbC++141.3kb2023-11-08 15:05:562023-11-08 15:05:56

Judging History

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

  • [2023-11-08 15:05:56]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:3404kb
  • [2023-11-08 15:05:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
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(){
    int n;
    cin>>n;
    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 check=[&](int mid){
      //      cout<<"check "<<mid<<endl;
            int x=query(pos[mid],i);
            int y=query(pos[mid]+1,i);
            return x^y^b[pos[mid]]^1;
        };
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid)){
                res=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
  //      cout<<"res > "<<res<<endl;
        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<<pos[i]<<" ";
        }
    //    cout<<endl;
    //    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: 3372kb

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: 56ms
memory: 3404kb

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 answer Wa.