QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226207#6303. InversionFreeuni1RE 1ms3500kbC++141.8kb2023-10-25 18:23:342023-10-25 18:23:35

Judging History

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

  • [2023-10-25 18:23:35]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3500kb
  • [2023-10-25 18:23:34]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>

using namespace std;
int dp[42][22][2], d[2003];
int dp1[42][22][2];
int cnt = 0;
vector<int> v;
map<pair<int, int>, int> q;
bool inv(int i1, int i2) {
    if (i2 < v.size()) {
        int ans = 0;
        for (int i = i1; i < v.size(); i ++) {
            ans += d[i];
        }
        //cout << "!" <<i1 << " " << i2 << " " << ans;
        return ans&1;
    }
    if (q[{i1, i2}]) {
        return q[{i1, i2}] - 1;
    }
    cnt ++;
    assert(cnt <= 40000);
    cout << "? " << i1 << " " << i2 << endl;
    int x;
    cin >> x;
    q[{i1, i2}] = x + 1;
    return x;
}

bool grt(int i1, int i2) {
    //cout << i1 << " " << i2 << endl;
    bool swp = false;
    if (i1 > i2) {
        swap(i1, i2);
        swp = true;
    }
    if (i2 - i1 == 1) {
        return inv(i1, i2) ^ swp;
    }
    if (i2 - i1 == 2) {
        return inv(i1, i2) ^ inv(i1 + 1, i2) ^ inv(i1, i2 - 1) ^ swp;
    }
    return inv(i1, i2) ^ inv(i1 + 1, i2) ^ inv(i1, i2 - 1) ^ inv(i1 + 1, i2 - 1) ^ swp;
}
main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> srt(n + 3);
    v.push_back(1);

    for (int i = 2; i <= n; i++) {
        int l = -1, r = v.size();
        while (r - l > 1) {
            //cout << l << " " << r << en
            int m = (l + r) / 2;
            if (grt(v[m], i)) {
                r = m;
            } else {
                l = m;
            }
        }
        v.insert(v.begin() + r, i);
        for (int j = r + 1; j < v.size(); j ++) {
            d[v[j]] ++;
        }
    }

    for (int i = 0; i < v.size(); i ++) {
        srt[v[i]] = i + 1;
    }
    cout << "! ";
    for (int i = 1; i <= n; i ++) {
        cout << srt[i] << " ";
    }
    cout << endl;
}
/*


*/

詳細信息

Test #1:

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

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Runtime Error

input:

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

output:

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

result: