QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96706#6303. Inversioncardinal_city#WA 455ms3596kbC++202.8kb2023-04-15 05:23:502023-04-15 05:23:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-15 05:23:54]
  • 评测
  • 测评结果:WA
  • 用时:455ms
  • 内存:3596kb
  • [2023-04-15 05:23:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

class BIT {
    private:
        vector<int> bit;
        int N;

        int lsone(int x) {
           // cout << "lsone " << (x & (-x)) << endl;
            return (x & (-x));
        }
    public:
    
        BIT(int n) {
            N = n+10;
            bit.resize(n+10);
        }

        void add(int idx) {
            idx++;
            for(;idx < N; idx += lsone(idx)) {
                bit[idx] += 1;
            }
        }

        int query(int idx) {
            idx++;
            int ans = 0;
            for(;idx > 0; idx -= lsone(idx)) {
             //   cout << idx << " " << lsone(idx) << endl;
                ans += bit[idx];
            }
            return ans;
        }

};

vector<int> ans(1);

void add(int p) {
    vector<int> pos(p);
    for(int i = 0; i < p; i++) pos[i] = i;
    shuffle(pos.begin(), pos.end(), default_random_engine{});
    // cout << "pos: ";
    // for(auto v : pos) cout << v << " ";
    // cout << endl;
    vector<int> numinv(p+1);
    BIT bit(p + 1);
    // cout << "ans: ";
    // for(auto v : ans) cout << v << " ";
    // cout << endl;
    for(int i = p - 1; i >= 0; i--) {
        numinv[i] = numinv[i+1];
        numinv[i] += bit.query(ans[i]);
        bit.add(ans[i]);
    }

    // cout << "numinv: ";
    // for(auto v : numinv) cout << v << " ";
    // cout << endl;



    // sort randomly

    vector<int> cand(p+1, 1);
    int numcand = p+1;
    int cnt = 0;

    vector<int> curr(p+1);
    while(numcand > 1) {
        for(int i = pos[cnt]; i < p; i++) {
            curr[ans[i]] = 1;
        }
        cout << "? " << pos[cnt] + 1 << " " << p + 1 << endl;
        int r; cin >> r;

        bool elim = true;

        if(r == (numinv[pos[cnt]])% 2) {
            elim = false;
        }

        for(int i = p; i >= 0; i--) {
            if(curr[i]) elim = !elim;
            if(elim) {
                if(cand[i] == 1) {
                    cand[i] = 0; numcand--;
                }
            }
        }

        for(int i = pos[cnt]; i < p; i++) {
            curr[ans[i]] = 0;
        }

        cnt++;
    }

    int newpos = 0;
    for(int i = 0; i <= p; i++) {
        if(cand[i] == 1) newpos = i;
    }

    vector<int> nans(p+1);
    for(int i = 0; i < p; i++) {
        if(ans[i] < newpos) {
            nans[i] = ans[i];
        } else {
            nans[i] = ans[i] + 1;
        }
    }
    nans[p] = newpos;

    swap(ans, nans);
}

int main() {
    // cin.tie(0)->sync_with_stdio(0);

    int n; cin >> n;

    for(int i = 1; i < n; i++) {
        add(i);
    }

    cout << "! ";
    for(auto x : ans) {
        cout << x + 1 << " ";
    }
    cout << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3396kb

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 455ms
memory: 3596kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected