QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210138#6303. InversionCedeatWA 56ms19008kbC++202.7kb2023-10-11 02:59:512023-10-11 02:59:51

Judging History

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

  • [2023-10-11 02:59:51]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:19008kb
  • [2023-10-11 02:59:51]
  • 提交

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 == r) return 1;
        bool ok = false;
        if (l > r) {
            swap(l, r);
            ok = true;
        }
        if (l + 1 == r) {
            return get(l, r) ^ ok;
        }
        int a = get(l, r);
        int b = get(l + 1, r);
        int c = get(l, r - 1);
        int d = get(l + 1, r - 1);
        if (ok) return (((a - b - c + d) % 2 + 2) % 2) ^ ok;
        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(i, rk[mid - 1])) {
                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;
            }
        }
    }
    cout << "! ";
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    } cout << endl;
}
// 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: 100
Accepted
time: 1ms
memory: 3840kb

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 56ms
memory: 19008kb

input:

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

output:

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

result:

wrong answer Wa.