QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #703834 | #6516. New but Nostalgic Problem | lllei# | AC ✓ | 20ms | 113588kb | C++20 | 1.4kb | 2024-11-02 18:38:48 | 2024-11-02 18:38:52 |
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[son[u][c]]);
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: 0ms
memory: 7940kb
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: 7692kb
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: 7ms
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: 0
Accepted
time: 19ms
memory: 7736kb
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:
ok 25000 lines
Test #5:
score: 0
Accepted
time: 10ms
memory: 86444kb
input:
1 898 840 fdefauodwerznqpzszernrspbndmdfkjrbazmworfvlfbxwcprhxenouzxirrhqtwgiwdcejexotjetwgzqlqtndynfzwmfakfeojtxwrvekebmudrouskcgpzncnsxwajwaoclvqnaycgaaktqctsmbnosbajzryxpxzxuwnzpvmyfobgogbllqyxplageeufjjnrlhairtetyridmhthpplivokbinfmblugrzkcyxuhewtyoxkfzmyhgsbafmgqazoqollibsxlprjneeqursjuomypstme...
output:
y
result:
ok single line: 'y'
Test #6:
score: 0
Accepted
time: 15ms
memory: 7740kb
input:
1 666416 645656 d j s g s b w x b z v m c o h a j v v l y i l n g x u q d m z q k n l c v n q b y g t c q i k b z i h e c b h e v a n c n z b g c n m f x q y b l h r a i g v e q k u e z q a a a c g d c d f n i d l d w i h p b a u n i e z l v l a y t k j y z r f c o f x w p y q a j v j n t f m j j z ...
output:
z
result:
ok single line: 'z'
Test #7:
score: 0
Accepted
time: 12ms
memory: 113588kb
input:
1 10 8 tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvju...
output:
tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvjupdzdlne...
result:
ok single line: 'tahlarajyplchghlbufhsanuvbmsaf...zlcmnrtuhonflpulivygwfecgknnhvx'
Test #8:
score: 0
Accepted
time: 11ms
memory: 83568kb
input:
1 10 3 fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpf...
output:
fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpfaxlmbsj...
result:
ok single line: 'fbggdpqikbolemnowgfpwwouvbmhhx...wwjgvkuxmlyqdleytyumnytyslycfmz'
Test #9:
score: 0
Accepted
time: 17ms
memory: 63328kb
input:
1 100 64 bqrjaovelwrainyujustjcnoyqpyeuqtpwbgafxsdcmjqbgbrqkzbwejfhxswzqjjibagmdkasztqqhxsubyliuwzetglnccigmzrhxrmrrptvywyavwpkqqsyhyuhdtstkqzlqbzvpacuevwrpinfzubzjgj bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmq...
output:
bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmqqahhykfsawtiatqczizqtmabdxqotpzhufebenhmnmbkavtbaqkpjloblntpbjhazyjtkakpeydymjnhgfsojzzucjvehkuvnefhkytpaasskzteisyylpukgkerhneqjqjkkqkigljadrneojmeyebyissomxlopckhtqz...
result:
ok single line: 'bqrjaovelwrainyujustjcnoyqpyeu...ulctwnloovccolzzlgjbonxkmtsflyq'
Test #10:
score: 0
Accepted
time: 14ms
memory: 64968kb
input:
1 1000 655 xrivmcvikmllrgissoqginwxkoqyxywrvspoagwvuycscxxldlmrszeuiiqzbcvkyvcogtqagprfubjza xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtygqrtviddhsqzpxauobucvondytzflgphhqgxkyaoihvvrqrvkbbleyn...
output:
xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtwiulbxpgqmqazceacggpluxdaxnjcrvcfxzthnkvjegomnbsmbfksetqxuxukwooizgrmgupxlnspeovfiuqyndkkgrzjwxxvpjopmjhknuavonvknpcxwlcjnvrdrvvqxinzktygkkjdhdoewkwx...
result:
ok single line: 'xrivmcvikmllrgissoqginwxkoqyxw...vsirnpcffpggcsscctonqrzhktybdfd'
Test #11:
score: 0
Accepted
time: 12ms
memory: 51032kb
input:
1 100000 60101 wbpwp wbtpv y wbmwmw wk wbi wpr wbmxw wms ttch x z wld wbmyu e wbmy ywa ws yw wv wbq ya x wx zp yl wt x wbddy wbwu y j x wbsvn x y y fwf wc yf z wcz ys wt z y xke zy wbt wbmwmvnoku wbu wbpikxn wbmx z x wbr zqt wbf wbq wr y z ye x y wtt ys wam z z yd wbmwzjdzk y z z wbpb wbtua z z x z ...
output:
x
result:
ok single line: 'x'
Test #12:
score: 0
Accepted
time: 20ms
memory: 113472kb
input:
1 15 3 accbbabccbbbaacaaabaacbacccbabaacbcbbaacbcabcbcabbbaabbbacaccbcacacbacbbbccbacaaabbaacbacbaacbcbbaaccbcbccbaabcbaacaccbbbccbbbccccbbcacacabaabccacccbcabacbbbbacbcaaababbbaacaababccbcacabcbaacccaaabbbcbcbcaaacabaacaabacbcbbccaabaccbbcbabcbcbabaabbbbabbcaacacbbcbabbabccabcbbbcbbbbcbaabcbcbacaba...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #13:
score: 0
Accepted
time: 13ms
memory: 18292kb
input:
1 300005 2 dei ytd scz rkd csj vhk spe vmf dep dhi afl vmyl xfg nno lgg gexx myx dhl ytk bdo sna znd xkm opt lwm ewr nsdtw pbx rqy dplgd znt sbw lga kvm xfe ewb dpz lyk spo ese dhb lcw jcb dhu poh lzw kybca ytw sbez eyx pfv sblv gew hcq yvi spy ewn spb znx xzn klj mna klp deuw ugv igu sbna yjli lwv ...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #14:
score: 0
Accepted
time: 15ms
memory: 94624kb
input:
1 8 2 aljyvnpjccrahfrixfoayvhxhwovfhsrjubibgwlxyhoryqxqlqbbpmszyogtslzmddmwkzwhjvnazabmzqeridgsukgosptmmbemzdfaezqiqedslcjkrlhjikiyzymeulnzxpnhhpbqnbdoqybnsbhesbgqbwfwyuggfnmeiceupezyjtzxhfspwrxnynxbeizewzejejkdfenecqhymgrvdgehzvahevwasmuboqwvblgbahyykskhiqtegqqylhknpbxxspyupyjufonsatqroxunkzenqoagq...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #15:
score: 0
Accepted
time: 20ms
memory: 108140kb
input:
1 10 5 badcbbacebabaaaaedeebfddecfcdfaccdeccdaffeaddafebdbedacabebbdacffdfeefebaabcbcafafbedacfbcadacfbeabafbeafdeacbdcfafcdfbbacbcbcbedecaedffceeccdfccdebaeeabfccbfdbebacfcebcebfafcfefaddfcacadccdfcfcefebbecdebadabffffecfcdababaddeeddfeccbbffdfabddaedeebcacbadbaadfaebaaaeecadfadbdadcdbdbbcbbfdeacdf...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #16:
score: 0
Accepted
time: 0ms
memory: 84772kb
input:
1 1005 796 fcfacbaaedfebebafefcaddfcbdeaeadcefdcebaabefbcfcaeddeebabaacbabdadaacfdaafdeebccfcbbffbecebfaaebdbbbbfcdadacfdababacaaacfdfcbdfeefeffbffadffcbbedfebdeefdeeeedcebeaecdbccdecdaefcfaccbabcaebdddffefeedeeafebaceafcdbadeaddcdfeaddafaaeccddbadefadafeebeccbfbceffaaddfbbbacfdacbeadcbeedcdfbecdfab...
output:
fbdfcffefdfefdabbbaaabbbdadbaecbbbfdaeaaefadaaeaacdaeecacfeccccddbedfdacaacdbdcdcaacecbbaabdccadfafdbdbdadbebfaafaeaaaacdecefdecefccacedeabcceabcfbcdeefbcabeddaeedbdaedacbeebaccbefddcdfcbaeaddfdfadadfadcbebccfbbbdbadcecfaceeefcfaebdedebdefdfaeefcedcffaeebcecbffacdcfcefefadaafbfdbadecefbfbfdceebbfcaff
result:
ok single line: 'fbdfcffefdfefdabbbaaabbbdadbae...fadaafbfdbadecefbfbfdceebbfcaff'
Test #17:
score: 0
Accepted
time: 14ms
memory: 84108kb
input:
1 1005 23 ecdafdebadceaebcadfaddbadfcbffbfaafdefecbfbceefaeeccabdaefefddfdccbcbeaeeefdedbadfcacedfabefeabcfdfcfadddadfeeeefcfeedcdcffeaedaffcdabecaecacaebddeaabcaabcebffeecafccdadacbbecbefedeefbebddcbadfdffdfabacddcdefeebddaddfdebafeffdeecaaedafebaceedfacadcdfcbdeafaaeeefcedcfdebfcbaddbdaefceaeafdca...
output:
adbcdacebaebdabbecbfdaebffefcfeaeafdaefefcffcbeeafaeebcfeddfaaaeecbabdbebeeaffebaebbfeeeafbfbfcacbdabbcafcecadbdcdccdddabaeeaacbcdfcbddbccdcaeaeeedcfefacddcbffcefbedabddddfaaffabffcbdbeafaceaaaadabeebbdedcbcbaceffcfdcfafbaeedaabcfabecfecacecdffccbaefabebceedcaadabcfbdbaeabfdccbbbeacefedbbcfbedfddbefae
result:
ok single line: 'adbcdacebaebdabbecbfdaebffefcf...abfdccbbbeacefedbbcfbedfddbefae'
Test #18:
score: 0
Accepted
time: 16ms
memory: 65344kb
input:
1 7 2 bebadebdcebccacabcabeebeebddebcaeceeebeeeadcaccecbccbeecbacbabbedcebdecebaacbedecdbdadcdbeacbabacbdaccbeacaaedeecbadecdabcaaeeecceebeaddbedeeeedbabbdebeddaabcaeeeaeeaeedcbbbbbdabbbdebaaaedaedcbabdceadcdbaaabdecdeabcbbdcbdaceacaddabbedbcadaeaeeedaaedcbeeebebcbceabecdbbcebadadcecddbbdeecbcdbedbb...
output:
EMPTY
result:
ok single line: 'EMPTY'