QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #703776 | #6516. New but Nostalgic Problem | lllei# | WA | 19ms | 7652kb | C++20 | 1.4kb | 2024-11-02 18:28:50 | 2024-11-02 18:28:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int son[maxn][26],cnt[maxn],val[maxn];
int idx=0;
void insert(string s)
{
int len=s.size(),cur=0;
for(int i=0;i<len;i++)
{
int c=s[i]-'a';
if(!son[cur][c])
{
son[cur][c]=++idx;
memset(son[idx],0,sizeof(son[idx]));
val[idx]=0;
cnt[idx]=0;
}
cur=son[cur][c];
cnt[cur]++;
}
val[cur]++;
}
vector<char>ans;
void dfs(int u,int now)
{
int sum=0;
for(int c=0;c<26;c++)if(cnt[son[u][c]])sum++;
if(sum>=now)return ;
for(int c=0;c<26;c++)
if(cnt[son[u][c]])
{
if(now-sum+1<=cnt[son[u][c]])
{
ans.push_back(c+'a');
dfs(son[u][c],now-sum+1-val[u]);
break;
}
sum+=cnt[son[u][c]]-1;
}
}
int n,k;
int T;
int main()
{
cin.tie(0);
ios::sync_with_stdio(0);
cin>>T;
while(T--)
{
ans.clear();
memset(son[0],0,sizeof(son[0]));
idx=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
insert(s);
}
dfs(0,k);
if(ans.size()==0)cout<<"EMPTY\n";
else
{
for(auto c:ans)cout<<c;
cout<<'\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7624kb
input:
2 5 3 gdcpc gdcpcpcp suasua suas sususua 3 3 a b c
output:
gdcpc EMPTY
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 17ms
memory: 7580kb
input:
20000 5 3 apveofpr irdbqk rnionnjjrk wrpihlsw ofylfsriof 5 4 iiltghqg kybhogptqf jfnmqxzrdq rpztcluq tzmnrcjae 5 5 ysp vujmkkcutl ksawqeiiaf waukilaq wmlsutlued 5 3 pikybt yiqmqvtjeq tyrsoihf vnvjrxpus cuubpacubb 5 2 rihuvikhg twrsuoervz ukiekoohw eysqgndpf sxswpeqtaf 5 5 vxzhicbp nvtdbgqal jilppvpt...
output:
EMPTY EMPTY w EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY o EMPTY EMPTY EMPTY EMPTY EMPTY t EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY w EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPT...
result:
ok 20000 lines
Test #3:
score: 0
Accepted
time: 11ms
memory: 7652kb
input:
1000 10 9 wkpbdhbivgksnwvnqnynzrmhowmpbbtswjydwidifwuquenplmozlqnkxqefckyzcughrdbturdzsxrcggpzrtrvlewigox qbxgxomnfarjtvfbxbabtpmhnuwvbxfpwpkjuzjsehofemfzxglvvthzgkzukwmlyfhajchvphdjfqmfubwwpdtdbjpfvk qrsovcdbphsndcmjwxjhmktwvgakzqewnoymumlawlmmgjmbpivccldrrfgspjypwosdqgpyqnxhaukwycqntuxglbdwf fbdtn...
output:
q EMPTY EMPTY EMPTY h EMPTY EMPTY EMPTY h EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY v b EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY t EMPTY EMPTY e EMPTY b EMPTY EMPTY EMPTY EMPTY EMPTY b EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY v EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPT...
result:
ok 1000 lines
Test #4:
score: -100
Wrong Answer
time: 19ms
memory: 7584kb
input:
25000 10 8 phl vwel ufme dtsf con giby xlma dhke zjir itws 9 5 qtgd wcqj ixmz swv myxo eqq yxiq uvb spbw 10 7 xrkp ze smt nq ijhw lmxf kcgs hi qwmq hilw 8 7 rlf taaq hmdu thex dbb spcp awyn khdu 10 10 voxx tqv ehtx xctk zamh zua rbyg bmeh wmiv cmw 9 6 bzq ayz cdna myi rdeu gtdo ycy sjec ystp 9 4 tix...
output:
EMPTY EMPTY EMPTY EMPTY z EMPTY EMPTY s EMPTY EMPTY EMPTY EMPTY EMPTY y EMPTY EMPTY a EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY m EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY g EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY j EMPTY EMPTY EMPTY EMPTY EMPTY j EMPTY t EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY ...
result:
wrong answer 3236th lines differ - expected: 'pfv', found: 'p'