QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#101903#6303. InversionayerszWA 172ms19340kbC++201.5kb2023-05-01 20:25:382023-05-01 20:25:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-01 20:25:40]
  • 评测
  • 测评结果:WA
  • 用时:172ms
  • 内存:19340kb
  • [2023-05-01 20:25:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2E3 + 5;

int rec[N][N];
int p[N];
int g[N];
int ans[N];
int n;

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

int check(int l, int r) {
    int a = query(l, r), b = query(l + 1, r);
    return ((a - b - g[l] + g[l + 1]) % 2 + 2) % 2;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 19252kb

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: 172ms
memory: 19340kb

input:

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

output:

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

result:

wrong answer Wa.