QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234222 | #6635. Strange Keyboard | ugly2333 | WA | 1258ms | 144044kb | C++20 | 1.5kb | 2023-11-01 14:58:04 | 2023-11-01 14:58:05 |
Judging History
answer
//Δ_E
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 1111111;
const int M = 26;
const int K = 5555;
const int inf = 1e9;
int n,k,l,w,rt,c[N][M],f[N],g[N],b[K],d[K],e[K],h[K];
char s[N],t[K];
vector<int> v,r;
int nw(){
w++;
memset(c[w],0,sizeof(c[w]));
g[w]=inf;
return w;
}
void ins(int&u,int i){
if(!u)
u=nw();
if(!s[i]){
g[u]=1;
v.push_back(u);
return;
}
ins(c[u][s[i]-'a'],i+1);
f[c[u][s[i]-'a']]=u;
}
int main(){
int T,i,j,o,x,u;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
for(i=0;i<k;i++)
b[i]=inf,d[i]=inf,e[i]=1;
w=0;
rt=nw();
v.clear();
for(i=1;i<=n;i++){
scanf("%s",s+1);
ins(rt,1);
x=strlen(s+1);
b[x%k]=min(b[x%k],x);
}
r.clear();
for(j=0;j<k;j++)
if(b[j]<inf)
r.push_back(j);
d[0]=0;
for(i=1;i<=k;i++){
o=-1;
x=inf+1;
for(j=0;j<k;j++)
if(e[j]&&x>d[j])
x=d[j],o=j;
if(x>=inf)
break;
e[o]=0;
for(u=0;u<r.size();u++){
j=r[u];
x=(o+j)%k;
d[x]=min(d[x],d[o]+(o+b[j])/k+1);
}
}
reverse(d+1,d+k);
for(i=1;i<k;i++)
d[i]++;
for(i=0;i<v.size();i++)
for(x=v[i],j=0;x;x=f[x],j++)
if(d[j%k]<inf)
g[x]=min(g[x],g[v[i]]+d[j%k]+j/k);
scanf("%s",t+1);
l=strlen(t+1);
for(i=0;i<=l;i++)
h[i]=inf;
h[0]=0;
for(i=0;i<l;i++)
if(h[i]<inf)
for(j=i,x=rt;j<=l&&x;j++,x=c[x][t[j]-'a'])
if(g[x]<inf)
h[j]=min(h[j],h[i]+g[x]);
printf("%d\n",h[l]>=inf?-1:h[l]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7760kb
input:
2 2 3 defgh abc abcde 1 1 a b
output:
3 -1
result:
ok 2 number(s): "3 -1"
Test #2:
score: 0
Accepted
time: 41ms
memory: 9816kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 187ms
memory: 7784kb
input:
10 446 4905 afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica afigcjhcgagabbiccehjcjajigghgbj...
output:
3 2 2 11 6 5 1 1 1 1
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 1258ms
memory: 7684kb
input:
100 140 4879 baabaababbababbaabababaaababbbabbbbbbabbababbbabbbbabbbbbbaabbbbbbbbabaabbbaabaabbbaabbabaabaabbbabbbababbbaabbabaaaaabbaaabbbabb baa baabaababbababbaabababaaababbbabbbbbbabbab baabaababbababbaabababaaabab baabaababbababbaabababaaababbbabbb baabaababbababbaabababaaababbbabbbbbbabbababbb...
output:
1 1 1 1 3 1 1 1 1 1 1 3 2 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 4 3 2 1 2 1 1 1 1 1 2 1 1 1 3 1 1 1 2 1 1 1 2 3 1 1 1 2 1 1 1 1 1 1 1 1 3 2 3 1 3 1 1 2 1 2 3 2 1 1 1 3 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 4 1
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 79ms
memory: 46888kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: 0
Accepted
time: 157ms
memory: 44308kb
input:
10 7 4923 baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...
output:
4287 228 3671 549 129 372 475 534 336 288
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 1210ms
memory: 14832kb
input:
100 7 4807 abbababaababbaabbabbaabaababbaaababaabaaabbaaaabababbbaabbaaabababbaabaabbaaaaabbbbaabbbaaabbbbabaabbbaaaaabbbaabbaaaabbaaababbaaabbbbabaabbababababbbabaaabaaaabbbbabbabbbbbaabaaabaababbabaaabbaabbabbabaaababbbabbabbbaababaabaaaabaaabbbbabbaabaababbbabbbbaaaabbabbbaabbaabbbbb aaaaababaaab...
output:
45 32 11 4 2475 132 50 330 20 6 99 25 126 6 4 14 74 108 208 11 5 67 166 2822 178 1307 548 92 386 493 279 2415 255 262 567 215 46 113 31 651 17 4 8 21 12 100 69 152 15 55 521 146 11 13 181 -1 442 1839 2 5 31 26 122 696 280 77 1 839 11 273 7 178 421 228 6 6 82 116 1 -1 293 519 5 160 15 126 13 31 619 4...
result:
ok 100 numbers
Test #8:
score: -100
Wrong Answer
time: 38ms
memory: 144044kb
input:
1 1 5000 abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
-1
result:
wrong answer 1st numbers differ - expected: '5023990000', found: '-1'