QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#299452#6303. InversionLittleXi#WA 132ms17456kbC++171.4kb2024-01-06 21:09:122024-01-06 21:09:12

Judging History

This is the latest submission verdict.

  • [2024-01-06 21:09:12]
  • Judged
  • Verdict: WA
  • Time: 132ms
  • Memory: 17456kb
  • [2024-01-06 21:09:12]
  • Submitted

answer

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int grid[2005][2005]={0};

int ask(int l,int r){
    cout<<"? "<<l+1<<" "<<r+1<<endl;
    int g = 0;
    cin>>g;
    return g;
}

int count(int l,int r){
    int sm = 0;
    for(int i =l;i<=r;i++)
        sm += grid[i][l];
    return sm%2;
}

void solve(){
    int n ;
    cin>>n;
    if(n==1){
        cout<<"! 1"<<endl;
        return;
    }
    vector<int> p(1,0);
    if(ask(0,1)){
        p = {1,0};
    }else p = {0,1};

    for(int i = 2;i<n;i++){
        
        int l = -1, r = p.size();

        while(l+1!=r){
            int m = l+r>>1;
            vector<int> inv = {ask(p[m],i),count(p[m],i-1),ask(p[m]+1,i),count(p[m]+1,i-1)};
            int comp = inv[0] - inv[1] -inv[2]+inv[3];
            comp = (comp%2+2)%2;
            if(comp) r = m;
            else l =m;
        }
        p.insert(p.begin()+r,i);
        
        vector<int> flg(n,0);
        for(int j = r+1;j<p.size();j++){
            flg[p[j]] = 1;
        }
        for(int j = i-1;j>=0;j--){
            grid[i][j] = grid[i][j+1] + flg[j];
        }


    }

    vector<int> ans(n,0);
    for(int i=0;i<n;i++){
        ans[p[i]] = i+1;
    }
    cout<<"! ";
    for(int x:ans) cout<<x<<" ";
    cout<<endl;

}


signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t = 1;
    // cin>>t;
    while(t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: 0
Accepted
time: 132ms
memory: 17456kb

input:

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

output:

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

result:

ok OK, guesses=38179

Test #3:

score: -100
Wrong Answer
time: 97ms
memory: 16496kb

input:

1887
1
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
1
1
0
0
0
1
0
0
0
0
0
0
1
1
0
1
0
0
1
0
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
0
1
0
0
1
1
0
1
1
0
1
0
0
0
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
0
0
1
0
1
0
1
1
0
0
1
0
1
0
0...

output:

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

result:

wrong answer Wa.