QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#375713 | #5116. Contests | World_Creater | WA | 4ms | 10152kb | C++14 | 1.7kb | 2024-04-03 15:07:16 | 2024-04-03 15:07:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,q,f[6][100005][17],a[6][100005],rk[6][100005];
int nw[6],nxt[6];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
rk[i][a[i][j]]=j;
}
}
for(int i=1;i<=m;i++)
{
memset(nw,0,sizeof(nw));
for(int j=n;j>=1;j--)
{
for(int k=1;k<=m;k++)
{
if(nw[k]==0||rk[k][a[i][j]]<rk[k][nw[k]])
{
nw[k]=a[i][j];
}
}
for(int k=1;k<=m;k++)
{
if(f[k][a[i][j]][0]==0||rk[k][nw[k]]<rk[k][f[k][a[i][j]][0]]) f[k][a[i][j]][0]=nw[k];
}
}
}
for(int i=1;(1<<i)<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=m;k++)
{
f[k][j][i]=f[k][j][i-1];
for(int t=1;t<=m;t++)
{
if(rk[f[k][f[t][j][i-1]][i-1]]<rk[f[k][j][i]]) f[k][j][i]=f[k][f[t][j][i-1]][i-1];
}
// cerr<<i<<" "<<j<<" "<<k<<" "<<f[k][j][i]<<"\n";
}
}
}
cin>>q;
while(q--)
{
int x,y;
cin>>x>>y;
if(x==y)
{
cout<<0<<"\n";
continue ;
}
bool fl=0;
for(int i=1;i<=m;i++)
{
if(rk[i][x]<rk[i][y])
{
cout<<"1\n";
fl=1;
break ;
}
}
if(fl) continue ;
int ans=0;
for(int i=1;i<=m;i++)
{
nw[i]=x;
}
for(int i=__lg(n);i>=0;i--)
{
memset(nxt,0,sizeof(nxt));
for(int j=1;j<=m;j++)
{
for(int k=1;k<=m;k++)
{
if(nxt[k]==0||rk[k][f[k][nw[j]][i]]<rk[k][nxt[k]])
{
nxt[k]=f[k][nw[j]][i];
}
}
}
bool fl=0;
for(int j=1;j<=m;j++)
{
if(rk[j][nxt[j]]<rk[j][y]) fl=1;
}
if(!fl)
{
ans+=1<<i;
memcpy(nw,nxt,sizeof(nxt));
}
}
cout<<ans+2<<"\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7724kb
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: 10152kb
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:
94 1025 1 1 1 21 1 154 1025 1 19 1025 25 1 1 1 80 1 1 1 1 1025 1 36 102 1 1 1 30 92 1 1 1025 37 36 60 1 1 1 1 1 1 1 1 16 1025 1025 1 1 1025 1025 1 1 142 1 1 77 1 60 1 1 1 4 90 1 1 1025 36 93 1 1 17 148 1 1 1 136 1025 1025 1 28 1025 1025 32 182 1 1025 1025 1 1 1 56 1025 75 25 115 122 1 1025 1 1 2 1 1...
result:
wrong answer 2nd numbers differ - expected: '-1', found: '1025'