QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#375467 | #5116. Contests | wsc2008 | WA | 0ms | 161880kb | C++14 | 1.9kb | 2024-04-03 11:09:37 | 2024-04-03 11:09:38 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
const ll N=2e5+9,B=10;
ll n,q,m,a[B][N],rk[B][N],nxt[20][B][N],go[B][B][N],f[B],g[B];
//nxt[i][j][k]: starting from k, jump 2^j steps, the best rank of contest i
bool chk(ll x,ll y){
rep(i,1,m){
if(a[i][x]>a[i][y])return 1;
}
return 0;
}
mt19937 rnd(time(0));
bool Med;
int main(){
cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
n=read(),m=read();
rep(i,1,m){
rep(j,1,n)a[i][j]=read();
}
// n=998,m=5;
// rep(i,1,m){
// rep(j,1,n)a[i][j]=j;
// }
rep(i,1,m){
rep(j,1,n)rk[i][a[i][j]]=j;
}
rep(i,1,m){
rep(j,1,m){
rep(k,1,n)go[i][j][k]=max(go[i][j][k-1],rk[j][a[i][k]]);
}
}
rep(i,1,n){
rep(j,1,m){
rep(k,1,m)nxt[0][j][i]=max(nxt[0][j][i],go[k][j][rk[k][i]-1]);
}
}
rep(p,1,17){
rep(i,1,m){
rep(j,1,n){
nxt[p][i][j]=nxt[p-1][i][j];
rep(k,1,m)nxt[p][i][j]=max(nxt[p][i][j],nxt[p-1][i][a[k][nxt[p-1][k][j]]]);
}
}
}
q=read();
while(q--){
ll y=read(),x=read();
if(chk(x,y)){
puts("1");
continue;
}
ll ans=0;
rep(i,1,m)f[i]=rk[i][x];
per(i,17,0){
memset(g,0,sizeof(g));
rep(j,1,m){
rep(k,1,m)g[j]=max(g[j],nxt[i][j][a[k][f[k]]]);
}
ll fl=0;
rep(j,1,m){
if(chk(a[j][g[j]],y)){
fl=1;
break;
}
}
if(!fl){
ans|=(1<<i);
rep(j,1,m)f[j]=g[j];
}
}
if(ans>n)puts("-1");
else write(ans+2),putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 73552kb
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: 0ms
memory: 161880kb
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 -1 1 1 1 21 1 153 -1 1 18 -1 25 1 1 1 80 1 1 1 1 -1 1 36 102 1 1 1 29 92 1 1 -1 37 37 60 1 1 1 1 1 1 1 1 16 -1 -1 1 1 -1 -1 1 1 141 1 1 77 1 60 1 1 1 3 91 1 1 -1 36 93 1 1 17 149 1 1 1 135 -1 -1 1 29 -1 -1 30 180 1 -1 -1 1 1 1 56 -1 75 25 115 121 1 -1 1 1 1 1 1 1 12 -1 1 -1 1 76 -1 128 -1 1 1 6 1...
result:
wrong answer 11th numbers differ - expected: '19', found: '18'