QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225531#6303. InversionFreeuni1#RE 0ms3640kbC++141.4kb2023-10-24 19:28:332023-10-24 19:28:34

Judging History

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

  • [2023-10-24 19:28:34]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3640kb
  • [2023-10-24 19:28:33]
  • 提交

answer

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

using namespace std;
int dp[42][22][2];
int dp1[42][22][2];
int cnt = 0;
bool inv(int i1, int i2) {
    cnt ++;
    assert(cnt < 40000);
    cout << "? " << i1 << " " << i2 << endl;
    int x;
    cin >> x;
    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> v, 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 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: 0ms
memory: 3640kb

input:

3
0
0
1
0

output:

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

result:

ok OK, guesses=4

Test #2:

score: -100
Runtime Error

input:

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

output:

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

result: