QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97633#6303. InversionayerszWA 188ms19236kbC++201.7kb2023-04-17 17:23:192023-04-17 17:23:21

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 17:23:21]
  • 评测
  • 测评结果:WA
  • 用时:188ms
  • 内存:19236kb
  • [2023-04-17 17:23:19]
  • 提交

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 pd(int l, int r) {
    if (l + 1 == r) {
        return query(l, r);
    }
    int A = norm(query(l, r - 1) - query(l + 1, r - 1));
    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 p[N], ans[N];
int cnt;

int main() {
    memset(rec, -1, sizeof rec);
    int n;
    scanf("%d", &n);
    cnt = 0;
    // while (true) {
    //     int l, r;
    //     cin >> l >> r;
    //     cout << pd(l, r) << "\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];
        }
        // cerr << "debug : " << ret << "\n";
        p[ret] = i;
    }
    // for (int i = 1; i <= n; i++) {
    //     cerr << p[i] << " ";
    // }
    // cerr << "\n";

    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: 2ms
memory: 19216kb

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: 188ms
memory: 19236kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected