QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376486#5116. Contestsfairyqq28WA 4ms76996kbC++141.6kb2024-04-04 10:42:432024-04-04 10:42:44

Judging History

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

  • [2024-04-04 10:42:44]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:76996kb
  • [2024-04-04 10:42:43]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 100010;
int n, m, q, a[10][N], mn[10];
struct node{
    int a[10];
    node() {memset(a, 0x3f, sizeof(a));}
    int& operator [] (const int& x) {return a[x];}
    int operator [] (const int& x) const {return a[x];}
    bool operator > (const node& x) const{
        rep(i, 1, m) if(a[i] <= x[i]) return 0;
        return 1;
    }
} rnk[N], f[N][17];

int main(){
    scanf("%d%d", &n, &m);
    rep(i, 1, m) rep(j, 1, n){
        scanf("%d", &a[i][j]);
        rnk[a[i][j]][i] = j;
    }
    rep(i, 1, m){
        memset(mn, 0x3f, sizeof(mn));
        per(j, n, 1){
            rep(k, 1, m) mn[k] = min(mn[k], rnk[a[i][j]][k]);
            rep(k, 1, m) f[j][0][k] = min(f[j][0][k], mn[k]);
        }
    }
    rep(k, 1, 16) rep(i, 1, n) rep(j, 1, m) rep(l, 1, m){
        f[i][k][j] = min(f[i][k][j], f[a[l][f[i][k-1][l]]][k-1][j]);
    }
    // printf("%d\n", f[6][1][1]);
    scanf("%d", &q);
    while(q--){
        int x, y; scanf("%d%d", &x, &y);
        if(!(rnk[x] > rnk[y])) {puts("1"); continue;}
        int ans = 0; node nw = rnk[x];
        per(i, 16, 0){
            node nxt;
            rep(j, 1, m) rep(k, 1, m)
                nxt[k] = min(nxt[k], f[a[j][nw[j]]][i][k]);
            if(nxt > rnk[y]) nw = nxt, ans += 1 << i;
        }
        if(ans > n) {puts("-1"); continue;}
        printf("%d\n", ans + 2);
    }
    return 0;
}

详细

Test #1:

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

input:

6 2
1 3 2 5 4 6
2 1 4 3 6 5
4
1 4
5 3
6 1
5 2

output:

1
2
5
3

result:

ok 4 number(s): "1 2 5 3"

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 76836kb

input:

998 5
1 2 6 3 4 5 7 11 8 9 14 12 13 10 15 16 18 19 20 17 23 22 21 26 24 25 27 29 30 28 32 31 34 33 37 38 39 35 40 36 41 43 42 46 44 48 45 47 51 49 50 56 52 57 53 54 55 62 58 59 63 64 60 65 66 61 67 69 70 68 71 73 74 75 72 78 77 79 82 76 81 85 84 80 86 87 83 88 90 91 89 92 96 98 94 95 97 101 93 103 1...

output:

-1
-1
1
1
1
26
1
-1
-1
1
25
-1
34
1
1
1
109
1
1
1
1
-1
1
-1
133
1
1
1
40
-1
1
1
-1
-1
41
-1
1
1
1
1
1
1
1
1
22
-1
-1
1
1
-1
-1
1
1
-1
1
1
-1
1
-1
1
1
1
4
115
1
1
-1
45
-1
1
1
24
-1
1
1
1
-1
-1
-1
1
36
-1
-1
45
-1
1
-1
-1
1
1
1
76
-1
-1
29
-1
-1
1
-1
1
1
2
1
1
1
17
-1
1
-1
1
100
-1
-1
-1
1
1
10
1
-1
...

result:

wrong answer 1st numbers differ - expected: '94', found: '-1'