QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303724#6303. InversionhammerWA 1ms3796kbC++172.1kb2024-01-12 22:16:472024-01-12 22:16:48

Judging History

This is the latest submission verdict.

  • [2024-01-12 22:16:48]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3796kb
  • [2024-01-12 22:16:47]
  • Submitted

answer

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

constexpr int mod = 1e9 + 7;
const int N = 2e3 + 10;
int asked[N][N];
int res[N][N];
int id2rank[N];
int rank2id[N];
int now;
int qcnt;
int query(int l, int r)
{
    // printf("q %d %d\n",l,r);
    if (l >= r)
        return 0;
    if (asked[l][r])
        return res[l][r];
    int ans = 0;
    if (r <= now) {
        for (int i = l; i < r; i++) {
            for (int j = i + 1; j <= r; j++) {
                if (id2rank[i] > id2rank[j]) {
                    ans ^= 1;
                }
            }
        }
    } else {
        qcnt++;
        assert(qcnt<=40000);
        printf("? %d %d\n", l, r);
        fflush(stdout);
        scanf("%d", &ans);
    }
    asked[l][r] = 1;
    res[l][r] = ans;
    return ans;
}
int cmp(int l, int r)
{
    int af = query(l, r);
    int sf = query(l + 1, r);
    int ad = query(l, r - 1);
    int sd = query(l + 1, r - 1);
    int ans = af ^ sf ^ ad ^ sd;
    // printf("ans %d\n", ans);
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
    id2rank[1] = 1;
    rank2id[1] = 1;
    for (int i = 2; i <= n; i++) {
        now=i-1;
        int L = 1, R = i;
        while (L < R) {
            int mid = L + R >> 1;
            // printf("L %d R %d cmp %d %d\n",L,R,rank2id[mid],i);
            if (!cmp(rank2id[mid], i)) {
                L = mid + 1;
            } else {
                R = mid;
            }
        }
        // L--;
        // printf("L %d\n", L);

        for (int x = i - 1; x >= L; x--) {
            id2rank[rank2id[x]]++;
            // rank2id[x+1]=rank2id[x];
        }
        id2rank[i] = L;
        for (int x = 1; x <= i; x++)
            rank2id[id2rank[x]] = x;
        // rank2id[L]=i;
        // puts("====");
        // for (int x = 1; x <= n; x++) {
        //     printf(" %d", rank2id[x]);
        // }
        // puts("--");
    }
    printf("!");
    for (int i = 1; i <= n; i++)
        printf(" %d", rank2id[i]);
    puts("");
    fflush(stdout);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3796kb

input:

3
0
1
0

output:

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

result:

wrong answer Wa.