QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210143#6303. InversionCedeatWA 0ms3528kbC++202.5kb2023-10-11 03:11:022023-10-11 03:11:04

Judging History

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

  • [2023-10-11 03:11:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3528kb
  • [2023-10-11 03:11:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...)                  \
    do {                           \
        std::cout << #x << " -> "; \
        err(x);                    \
    } while (0)

void err() {
    std::cout << std::endl;
}

template <class T, class... Ts>
void err(T arg, Ts ...args) {
    std::cout << arg << ' ';
    err(args...);
}

using ll = long long;

void Solve(int tCase) {
    int n;
    cin >> n;
    vector f(n + 1, vector<int> (n + 1, -1));
    int tot = 0;
    auto ask = [&] (int l, int r) {
        if (l == r) return 0;
        ++tot;
        assert(tot <= 40000);
        cout << "? " << l << ' ' << r << endl;
        int x;
        cin >> x;
        return x;
    };
    auto get = [&] (int l, int r) {
        if (f[l][r] == -1) {
            return f[l][r] = ask(l, r);
        }
        return f[l][r];
    };
    auto check = [&] (int l, int r) {
        if (l + 1 == r) {
            return get(l, r);
        }
        int a = get(l, r);
        int b = get(l + 1, r);
        int c = get(l, r - 1);
        int d = get(l + 1, r - 1);
        return (((a - b - c + d) % 2 + 2) % 2);
    };
    vector<int> rk(n + 1), ans(n + 1);
    rk[1] = 1;
    ans[1] = 1;
    for (int i = 2; i <= n; i++) {
        int l = 1, r = i;
        // dbg(i);
        while (l < r) {
            int mid = l + r + 1 >> 1;
            // dbg(mid, l, r);
            // if (mid == 1) break;
            if (mid == 1 || check(rk[mid - 1], i)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        for (int j = i; j > l; j--) {
            ans[rk[j - 1]]++;
            rk[j] = rk[j - 1];
        }
        rk[l] = i;
        ans[i] = l;
        // for (int i = 1; i <= n; i++) {
        //     cout << ans[i] << ' ';
        // } cout << endl;
        // for (int i = 1; i <= n; i++) {
        //     cout << rk[i] << ' ';
        // } cout << endl;
        // dbg(l);
        int cnt = 0;
        for (int j = i - 1; j >= 1; j--) {
            if (ans[j] > ans[i]) cnt++;
            if (f[j][i] == -1) {
                f[j][i] = (f[j][i - 1] + cnt) % 2;
            }
        }
    }
    cout << "! ";
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    } cout << endl;
}
// 2 1 3 4
// 1 2 3
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    for (int t = 1; t <= T; ++t) {
        Solve(t);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3528kb

input:

3
0
1
0

output:

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

result:

wrong answer Wa.