QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97667#6303. InversionayerszWA 210ms19480kbC++201.5kb2023-04-17 20:53:452023-04-17 20:53:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-17 20:53:46]
  • 评测
  • 测评结果:WA
  • 用时:210ms
  • 内存:19480kb
  • [2023-04-17 20:53:45]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2005;

int rec[N][N];

int query(int l, int r) {
    if (rec[l][r] != -1) {
        return rec[l][r];
    }
    if (l == r) {
        return 0;
    }
    printf("? %d %d\n", l, r);
    fflush(stdout);

    int ret;
    scanf("%d", &ret);
    return rec[l][r] = ret;
}

int norm(int x) { return (x % 2 + 2) % 2; }

// 0:a[l]<a[r], 1:a[l]>a[r]

int p[N], ans[N];
int cnt;

int calcXy(int l, int r, int x) {
    int ret = 0;
    for (int i = l; i <= r; i++) {
        if (p[i] < x) {
            ret++;
        }
    }
    return ret;
}

int pd(int l, int r) {
    if (l + 1 == r) {
        return query(l, r);
    }
    int C = 0;
    int A = norm(calcXy(l + 1, r - 1, p[l]));
    int B = norm(query(l + 1, r) - query(l + 1, r - 1));
    return norm(query(l, r) - A - B - query(l + 1, r - 1));
}

int main() {
    memset(rec, -1, sizeof rec);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int l = 1, r = i - 1, ret = i;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (pd(p[mid], i)) {
                ret = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        for (int j = i; j > ret; j--) {
            p[j] = p[j - 1];
        }
        p[ret] = i;
    }
    for (int i = 1; i <= n; i++) {
        ans[p[i]] = i;
    }
    printf("!");
    for (int i = 1; i <= n; i++) {
        printf(" %d", ans[i]);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 19236kb

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 210ms
memory: 19480kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected