QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226215#6303. InversionFreeuni1WA 1ms3804kbC++141.8kb2023-10-25 18:28:322023-10-25 18:28:32

Judging History

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

  • [2023-10-25 18:28:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3804kb
  • [2023-10-25 18:28:32]
  • 提交

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;
            cout << "     " << m << endl;
            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: 0
Wrong Answer
time: 1ms
memory: 3804kb

input:

3

output:

     0
? 1 2

result:

wrong output format Unexpected end of file - int32 expected