QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488054 | #6635. Strange Keyboard | ucup-team052# | WA | 341ms | 56480kb | C++23 | 1.9kb | 2024-07-23 15:45:33 | 2024-07-23 15:45:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, M = 5005;
const int inf=0x3f3f3f3f;
char s[N];
int len[N],n,k,dis[M];
int ch[N][26],w[N],dep[N],cnt,m,mnl[M];
vector<int> v[N];
int f[M];
vector<int> can;
struct Node
{
int id,val;
Node(int a=0,int b=0) {id=a,val=b;}
bool operator < (const Node &x) const {return val>x.val;}
};
void init()
{
for(int i=0;i<k;i++) dis[i]=inf;
dis[0]=0;
priority_queue<Node> q;
q.emplace(0,0);
while(!q.empty())
{
auto [v,w]=q.top(); q.pop();
if(dis[v]!=w) continue;
for(int l:can)
{
int tl=(v+l)%k;
int tw=dis[v]+(v+mnl[l])/k;
if(dis[tl]>tw) dis[tl]=tw,q.emplace(tl,tw);
}
}
for(int i=1;i<=cnt;i++)
{
w[i]=inf;
for(int j:v[i])
{
int cl=(len[j]-dep[i]);
int cw=cl/k+dis[cl%k];
w[i]=min(w[i],cw);
}
}
}
void ins(int len,int id)
{
int cur=0;
for(int i=1;i<=len;i++)
{
if(!ch[cur][s[i]-'a']) ch[cur][s[i]-'a']=++cnt,dep[cnt]=dep[cur]+1;
cur=ch[cur][s[i]-'a'];
v[cur].push_back(id);
}
}
void work()
{
cin>>n>>k;
for(int i=0;i<=cnt;i++) for(int j=0;j<26;j++) ch[i][j]=0;
cnt=0;
for(int i=0;i<k;i++) mnl[i]=inf;
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
len[i]=strlen(s+1);
mnl[len[i]%k]=min(mnl[len[i]%k],len[i]);
ins(len[i],i);
}
can.clear();
for(int i=0;i<k;i++) if(mnl[i]!=inf) can.push_back(mnl[i]);
// for(int i:can) printf("%d ",i); cout<<"\n";
init();
scanf("%s",s+1); m=strlen(s+1);
f[0]=0; for(int i=1;i<=m;i++) f[i]=inf;
for(int i=0;i<m;i++)
{
if(f[i]==inf) continue;
int cur=0;
for(int j=i+1;j<=m;j++)
{
if(!ch[cur][s[j]-'a']) break;
cur=ch[cur][s[j]-'a'];
f[j]=min(f[j],f[i]+1+w[cur]);
}
}
if(f[m]==inf) printf("-1\n");
else printf("%d\n",f[m]);
}
int main() {
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
work();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9936kb
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: 31ms
memory: 18104kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 97ms
memory: 15300kb
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: 341ms
memory: 14812kb
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: -100
Wrong Answer
time: 84ms
memory: 56480kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
127
result:
wrong answer 1st numbers differ - expected: '205', found: '127'