QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #141238 | #6516. New but Nostalgic Problem | cy1999 | WA | 53ms | 5780kb | C++20 | 1.4kb | 2023-08-17 09:56:03 | 2023-08-17 09:56:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int son[N][26],idx,cnt[N],sfx[N][27];
int n,k;
void ins(const string &s){
int p=0;
for(int i=0; i<s.size(); i++){
cnt[p]++;
if(!son[p][s[i]-'a']) son[p][s[i]-'a']=++idx;
p=son[p][s[i]-'a'];
}
cnt[p]++;
}
void init(int p){
for(int i=25; ~i; i--){
if(i!=25) sfx[p][i]=sfx[p][i+1];
if(son[p][i]) sfx[p][i]+=(cnt[son[p][i]]>0?1:0);
if(son[p][i]) init(son[p][i]);
}
}
string dfs(int p,int k){
if(k<=sfx[p][0]) return "";
int sum=0;
string ret;
for(int i=0; i<26; i++){
if(!son[p][i]) continue;
if(sum+sfx[p][i+1]+cnt[son[p][i]]>=k&&cnt[son[p][i]]>1){
return dfs(son[p][i],k-sum-sfx[p][i+1])+(char)('a'+i);
}
sum+=cnt[son[p][i]];
}
return "";
}
void solve(){
for(int i=0; i<=idx+6; i++){
for(int j=0; j<26; j++) son[i][j]=0,sfx[i][j]=0;
cnt[i]=0;
}
idx=0;
cin>>n>>k;
for(int i=1; i<=n; i++){
string t;
cin>>t;
ins(t);
}
init(0);
string ans=dfs(0,k);
if(!ans.size()){
cout<<"EMPTY\n";
return ;
}
reverse(ans.begin(),ans.end());
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--) solve();
return 0;
}
/*
2
5 3
gdcpc
gdcpcpcp
suasua
suas
sususua
3 3
a
b
c
1
8 4
ab
ac
bb
bc
cc
cb
db
dc
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5524kb
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: 42ms
memory: 5544kb
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: 40ms
memory: 5780kb
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: 53ms
memory: 5644kb
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'