QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #357920 | #6516. New but Nostalgic Problem | PorNPtree# | AC ✓ | 50ms | 145100kb | C++14 | 1.8kb | 2024-03-19 15:01:00 | 2024-03-19 15:01:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
string s[N];
int ch[26][N], S[N], zc[N];
signed main()
{
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
int tot = 1;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
int now = 1;
for (int j = 0; j < (int)s[i].size(); ++j) {
int k = s[i][j] - 'a';
if (!ch[k][now]) {
ch[k][now] = ++tot;
}
now = ch[k][now];
++S[now];
}
++zc[now];
}
string res = "";
int now = 1;
while (m > 0) {
if (zc[now]) {
m -= zc[now];
if (m <= 0) {
break;
}
}
int ct = 0;
for (int i = 0; i < 26; ++i) {
ct += !!ch[i][now];
}
if (ct >= m) {
break;
}
int z = ct;
for (int i = 0; i < 26; ++i) {
if (!ch[i][now]) {
continue;
}
z += S[ch[i][now]] - 1;
if (z >= m) {
res += (char)(i + 'a');
m -= z - S[ch[i][now]];
now = ch[i][now];
break;
}
}
}
if (res == "") {
puts("EMPTY");
} else {
puts(res.c_str());
}
for (int j = 0; j < 26; ++j) {
for (int i = 1; i <= tot; ++i) {
ch[j][i] = 0;
zc[i] = S[i] = 0;
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 35292kb
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: 31ms
memory: 35252kb
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: 19ms
memory: 35028kb
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: 47ms
memory: 34972kb
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: 44ms
memory: 115128kb
input:
1 898 840 fdefauodwerznqpzszernrspbndmdfkjrbazmworfvlfbxwcprhxenouzxirrhqtwgiwdcejexotjetwgzqlqtndynfzwmfakfeojtxwrvekebmudrouskcgpzncnsxwajwaoclvqnaycgaaktqctsmbnosbajzryxpxzxuwnzpvmyfobgogbllqyxplageeufjjnrlhairtetyridmhthpplivokbinfmblugrzkcyxuhewtyoxkfzmyhgsbafmgqazoqollibsxlprjneeqursjuomypstme...
output:
y
result:
ok single line: 'y'
Test #6:
score: 0
Accepted
time: 50ms
memory: 34984kb
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: 48ms
memory: 145100kb
input:
1 10 8 tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvju...
output:
tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvjupdzdlne...
result:
ok single line: 'tahlarajyplchghlbufhsanuvbmsaf...zlcmnrtuhonflpulivygwfecgknnhvx'
Test #8:
score: 0
Accepted
time: 41ms
memory: 112548kb
input:
1 10 3 fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpf...
output:
fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpfaxlmbsj...
result:
ok single line: 'fbggdpqikbolemnowgfpwwouvbmhhx...wwjgvkuxmlyqdleytyumnytyslycfmz'
Test #9:
score: 0
Accepted
time: 30ms
memory: 91292kb
input:
1 100 64 bqrjaovelwrainyujustjcnoyqpyeuqtpwbgafxsdcmjqbgbrqkzbwejfhxswzqjjibagmdkasztqqhxsubyliuwzetglnccigmzrhxrmrrptvywyavwpkqqsyhyuhdtstkqzlqbzvpacuevwrpinfzubzjgj bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmq...
output:
bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmqqahhykfsawtiatqczizqtmabdxqotpzhufebenhmnmbkavtbaqkpjloblntpbjhazyjtkakpeydymjnhgfsojzzucjvehkuvnefhkytpaasskzteisyylpukgkerhneqjqjkkqkigljadrneojmeyebyissomxlopckhtqz...
result:
ok single line: 'bqrjaovelwrainyujustjcnoyqpyeu...ulctwnloovccolzzlgjbonxkmtsflyq'
Test #10:
score: 0
Accepted
time: 33ms
memory: 92384kb
input:
1 1000 655 xrivmcvikmllrgissoqginwxkoqyxywrvspoagwvuycscxxldlmrszeuiiqzbcvkyvcogtqagprfubjza xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtygqrtviddhsqzpxauobucvondytzflgphhqgxkyaoihvvrqrvkbbleyn...
output:
xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtwiulbxpgqmqazceacggpluxdaxnjcrvcfxzthnkvjegomnbsmbfksetqxuxukwooizgrmgupxlnspeovfiuqyndkkgrzjwxxvpjopmjhknuavonvknpcxwlcjnvrdrvvqxinzktygkkjdhdoewkwx...
result:
ok single line: 'xrivmcvikmllrgissoqginwxkoqyxw...vsirnpcffpggcsscctonqrzhktybdfd'
Test #11:
score: 0
Accepted
time: 39ms
memory: 79392kb
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: 34ms
memory: 145088kb
input:
1 15 3 accbbabccbbbaacaaabaacbacccbabaacbcbbaacbcabcbcabbbaabbbacaccbcacacbacbbbccbacaaabbaacbacbaacbcbbaaccbcbccbaabcbaacaccbbbccbbbccccbbcacacabaabccacccbcabacbbbbacbcaaababbbaacaababccbcacabcbaacccaaabbbcbcbcaaacabaacaabacbcbbccaabaccbbcbabcbcbabaabbbbabbcaacacbbcbabbabccabcbbbcbbbbcbaabcbcbacaba...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #13:
score: 0
Accepted
time: 32ms
memory: 43096kb
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: 34ms
memory: 123144kb
input:
1 8 2 aljyvnpjccrahfrixfoayvhxhwovfhsrjubibgwlxyhoryqxqlqbbpmszyogtslzmddmwkzwhjvnazabmzqeridgsukgosptmmbemzdfaezqiqedslcjkrlhjikiyzymeulnzxpnhhpbqnbdoqybnsbhesbgqbwfwyuggfnmeiceupezyjtzxhfspwrxnynxbeizewzejejkdfenecqhymgrvdgehzvahevwasmuboqwvblgbahyykskhiqtegqqylhknpbxxspyupyjufonsatqroxunkzenqoagq...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #15:
score: 0
Accepted
time: 15ms
memory: 138836kb
input:
1 10 5 badcbbacebabaaaaedeebfddecfcdfaccdeccdaffeaddafebdbedacabebbdacffdfeefebaabcbcafafbedacfbcadacfbeabafbeafdeacbdcfafcdfbbacbcbcbedecaedffceeccdfccdebaeeabfccbfdbebacfcebcebfafcfefaddfcacadccdfcfcefebbecdebadabffffecfcdababaddeeddfeccbbffdfabddaedeebcacbadbaadfaebaaaeecadfadbdadcdbdbbcbbfdeacdf...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #16:
score: 0
Accepted
time: 35ms
memory: 113456kb
input:
1 1005 796 fcfacbaaedfebebafefcaddfcbdeaeadcefdcebaabefbcfcaeddeebabaacbabdadaacfdaafdeebccfcbbffbecebfaaebdbbbbfcdadacfdababacaaacfdfcbdfeefeffbffadffcbbedfebdeefdeeeedcebeaecdbccdecdaefcfaccbabcaebdddffefeedeeafebaceafcdbadeaddcdfeaddafaaeccddbadefadafeebeccbfbceffaaddfbbbacfdacbeadcbeedcdfbecdfab...
output:
fbdfcffefdfefdabbbaaabbbdadbaecbbbfdaeaaefadaaeaacdaeecacfeccccddbedfdacaacdbdcdcaacecbbaabdccadfafdbdbdadbebfaafaeaaaacdecefdecefccacedeabcceabcfbcdeefbcabeddaeedbdaedacbeebaccbefddcdfcbaeaddfdfadadfadcbebccfbbbdbadcecfaceeefcfaebdedebdefdfaeefcedcffaeebcecbffacdcfcefefadaafbfdbadecefbfbfdceebbfcaff
result:
ok single line: 'fbdfcffefdfefdabbbaaabbbdadbae...fadaafbfdbadecefbfbfdceebbfcaff'
Test #17:
score: 0
Accepted
time: 35ms
memory: 113416kb
input:
1 1005 23 ecdafdebadceaebcadfaddbadfcbffbfaafdefecbfbceefaeeccabdaefefddfdccbcbeaeeefdedbadfcacedfabefeabcfdfcfadddadfeeeefcfeedcdcffeaedaffcdabecaecacaebddeaabcaabcebffeecafccdadacbbecbefedeefbebddcbadfdffdfabacddcdefeebddaddfdebafeffdeecaaedafebaceedfacadcdfcbdeafaaeeefcedcfdebfcbaddbdaefceaeafdca...
output:
adbcdacebaebdabbecbfdaebffefcfeaeafdaefefcffcbeeafaeebcfeddfaaaeecbabdbebeeaffebaebbfeeeafbfbfcacbdabbcafcecadbdcdccdddabaeeaacbcdfcbddbccdcaeaeeedcfefacddcbffcefbedabddddfaaffabffcbdbeafaceaaaadabeebbdedcbcbaceffcfdcfafbaeedaabcfabecfecacecdffccbaefabebceedcaadabcfbdbaeabfdccbbbeacefedbbcfbedfddbefae
result:
ok single line: 'adbcdacebaebdabbecbfdaebffefcf...abfdccbbbeacefedbbcfbedfddbefae'
Test #18:
score: 0
Accepted
time: 27ms
memory: 92704kb
input:
1 7 2 bebadebdcebccacabcabeebeebddebcaeceeebeeeadcaccecbccbeecbacbabbedcebdecebaacbedecdbdadcdbeacbabacbdaccbeacaaedeecbadecdabcaaeeecceebeaddbedeeeedbabbdebeddaabcaeeeaeeaeedcbbbbbdabbbdebaaaedaedcbabdceadcdbaaabdecdeabcbbdcbdaceacaddabbedbcadaeaeeedaaedcbeeebebcbceabecdbbcebadadcecddbbdeecbcdbedbb...
output:
EMPTY
result:
ok single line: 'EMPTY'