QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96553#6303. Inversionhath19260817WA 268ms17272kbC++201.5kb2023-04-14 14:40:372023-04-14 14:40:39

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-14 14:40:39]
  • 评测
  • 测评结果:WA
  • 用时:268ms
  • 内存:17272kb
  • [2023-04-14 14:40:37]
  • 提交

answer

#include <cstdio>
#include <cstring>

const int maxn = 2e3 + 5;
int f[maxn][maxn], rk[maxn], ans[maxn], pos[maxn], n = 0;

int ask(int x, int y) {
    if (f[x][y] != -1)
        return f[x][y];
    printf("? %d %d\n", x, y);
    fflush(stdout);
    scanf("%d", &f[x][y]);
    return f[x][y];
}

int ask_local(int x, int y) {
    if (f[x][y] != -1)
        return f[x][y];
    if (y == x + 1)
        return pos[x] > pos[y];
    return f[x][y] = ((ask_local(x + 1, y) + ask_local(x, y - 1) - ask_local(x + 1, y - 1) + (pos[x] > pos[y]) + 8) & 1);
}

int query(int x, int y) {
    if (y == x + 1)
        return ask(x, y);
    return (ask(x, y) - ask_local(x, y - 1) - ask(x + 1, y) + ask_local(x + 1, y - 1) + 8) & 1;
}

int get_pos(int x) {
    int l = 1, r = rk[0], ans = 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (query(rk[mid], x))
            r = mid - 1;
        else
            l = mid + 1, ans = l;
    }
    return ans;
}

int main() {
    memset(f, -1, sizeof(f));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        f[i][i] = 0;
    rk[0] = rk[1] = 1;
    for (int i = 2; i <= n; ++i) {
        int p = get_pos(i);
        for (int j = rk[0]; j >= p; --j)
            rk[j + 1] = rk[j], ++pos[rk[j]];
        rk[p] = i, ++rk[0], pos[rk[p]] = i;
    }
    for (int i = 1; i <= n; ++i)
        ans[rk[i]] = i;
    putchar('!');
    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: 17212kb

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: 268ms
memory: 17272kb

input:

1993
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
1
1
1
0
0
1
0
0
1
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
1
1
1
1
0
1
0
0
1
0
0
0
1
1
0
0
0
1
1
0
1
1
1
1
1
0
1
1
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
? 1 9
? 2 9
? 8 9
? 3 9
? 9 10
? 5 10
? 6 10
? 7 10
? 8 10
? 1 11
? 2 11
? 10 11
? 5 11
? 6 11
? 7 11
? 1 12
? 2 12
? 8 12
? 9 12
? 3 12
? 4 12
? 5 12
? 1 13
? 2 13
? 8 13
? 9 13
?...

result:

wrong answer Wa.