QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#376436	#5116. Contests	fzx	WA	4ms	232972kb	C++14	2.3kb	2024-04-04 09:57:22	2024-04-04 09:57:23

Judging History

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

[2024-04-04 09:57:23]
评测

测评结果：WA
用时：4ms
内存：232972kb

查看

[2024-04-04 09:57:22]
提交

answer

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int INF=1e5+5;
int n,m,a[7][INF],f[35][7][INF],aa[7][7][INF],rr[7],p3[7][INF],ll[7];
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        for (int j=1;j<=n;j++)
            cin>>a[i][j];
    }
    for (int i=1;i<=m;i++) {
        for (int j=1;j<=n;j++) p3[i][a[i][j]]=j;
        for (int p=1;p<=m;p++) {
            aa[i][p][n+1]=1e9;
            for (int j=n;j;j--) 
                aa[i][p][j]=min(aa[i][p][j+1],p3[i][a[p][j]]);    
        }
    }
    // p3[i][j] 表示 在 i 这场比赛中，j 这个点 的排名
    // aa[i][p][j] 在第 p 场比赛中， j 这个排名之后，在 i 这场比赛的最小值
    memset(f,63,sizeof f);
    for (int x=1;x<=m;x++)
        for (int y=1;y<=m;y++)
            for (int j=1;j<=n;j++) {
                f[0][x][j]=min(f[0][x][j],aa[x][y][p3[y][j]]);
            }
    for (int i=1;i<20;i++) {
        for (int x=1;x<=m;x++) {
            for (int y=1;y<=m;y++) {
                for (int j=1;j<=n;j++) {
                    f[i][x][j]=min(f[i-1][x][a[y][f[i-1][y][j]]],f[i][x][j]);
                }
            }
        }
    }

    int q=0;cin>>q;
    while (q--) {
        int l=0,r=0,res=0;
        cin>>l>>r;
        if (l==r) {cout<<"0\n";continue;}
        int fl5=0;
        for (int i=1;i<=m;i++)
            if (p3[i][l]<p3[i][r]) {cout<<"1\n";fl5=1;break;}
        if (fl5) continue;
        for (int u=1;u<=m;u++) ll[u]=l;
        int fl3=0;
        for (int p=19;~p;p--) {
            int fl2=0;
            for (int u=1;u<=m;u++) {
                int fl=0;
                for (int v=1;v<=m;v++) 
                    if (p3[v][a[u][f[p][u][ll[u]]]]<p3[v][r]) fl=1;
                if (fl) fl2=1;
            }
            if (fl2) fl3=1;
            else {
                res|=(1ll<<p);
                for (int u=1;u<=m;u++) {
                    int fl=1e18;
                    for (int v=1;v<=m;v++) 
                        fl=min(fl,f[p][u][ll[v]]);
                    rr[u]=a[u][fl];
                }
                for (int u=1;u<=m;u++) ll[u]=rr[u];
            }
        }
        if (!fl3) cout<<"-1\n"; 
        else cout<<res+2<<"\n";
    }
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 208360kb

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:

result:

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

Test #2:

score: -100

Wrong Answer

time: 4ms

memory: 232972kb

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:

result:

wrong answer 11th numbers differ - expected: '19', found: '20'