QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303728#6303. InversionhammerTL 0ms3652kbC++171.8kb2024-01-12 22:22:112024-01-12 22:22:12

Judging History

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

  • [2024-01-12 22:22:12]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3652kb
  • [2024-01-12 22:22:11]
  • 提交

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--;

        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;
    }
    printf("!");
    for (int i = 1; i <= n; i++)
        printf(" %d", id2rank[i]);
    puts("");
    fflush(stdout);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Time Limit Exceeded

input:

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

output:

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

result: