QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #355001 | #6516. New but Nostalgic Problem | RDFZchenyy | WA | 16ms | 7928kb | C++14 | 1.5kb | 2024-03-16 10:33:25 | 2024-03-16 10:33:26 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
int n,k;
string t;
inline int ind(char x){return x-96;}
int tr[2000001][28];
int siz[2000001];
int typ[2000001];
int cnt=0;
void add(string s)
{
int cur=0;
for(int i=0;i<s.size();i++) s[i]=ind(s[i]);
for(int i=0;i<s.size();i++)
{
//cout<<cur<<" "<<(int)s[i]<<endl;
siz[cur]++;
if(!tr[cur][s[i]]) tr[cur][s[i]]=++cnt,typ[cur]++;
cur=tr[cur][s[i]];
}
siz[cur]++;
}
string sol(int k)
{
string ans="";int left=k,nowsiz=0,cur=0;
while(1)
{
if(typ[cur]>=k) return ans;
k-=typ[cur];left=k;//cout<<k<<" "<<nowsiz<<endl;
for(int i=1;i<=26;i++)
{
if(tr[cur][i]==0) continue;
if(left<=siz[tr[cur][i]]-1)
{
k=left;
ans+=(char)(i+96);
cur=tr[cur][i];
k++;
break;
}
else left-=siz[tr[cur][i]]-1;
}
if(nowsiz==ans.size()) return ans;
//cout<<k<<" "<<ans<<" "<<nowsiz<<endl;
nowsiz=ans.size();
}
}
signed main()
{
std::ios::sync_with_stdio(false);
cin>>T;while(T--){
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=27;j++) tr[i][j]=0;
siz[i]=typ[i]=0;
}cnt=0;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>t,add(t);
//for(int i=1;i<=cnt;i++) cout<<siz[i]<<endl;
t=sol(k);
if(t=="") cout<<"EMPTY\n";
else cout<<t<<endl;
}return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7660kb
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: 11ms
memory: 7668kb
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: 10ms
memory: 7740kb
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: 16ms
memory: 7928kb
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'