QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110693 | #6516. New but Nostalgic Problem | hos_lyric | AC ✓ | 57ms | 113212kb | C++14 | 3.1kb | 2023-06-03 12:40:39 | 2023-06-03 12:40:41 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
constexpr int MAX = 1'000'010;
constexpr int A = 26;
int N, K;
char S[MAX];
int V;
int nxt[MAX][A];
int cnt[MAX], fs[MAX];
int newNode() {
const int u = V++;
memset(nxt[u], ~0, sizeof(nxt[u]));
cnt[u] = fs[u] = 0;
return u;
}
int main() {
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
scanf("%d%d", &N, &K);
V = 0;
newNode();
for (int i = 0; i < N; ++i) {
scanf("%s", S);
int u = 0;
for (int x = 0; S[x]; ++x) {
const int a = S[x] - 'a';
int &v = nxt[u][a];
if (!~v) v = newNode();
u = v;
}
++cnt[u];
}
for (int u = V; --u >= 0; ) {
fs[u] = cnt[u];
for (int a = 0; a < A; ++a) {
const int v = nxt[u][a];
if (~v) {
fs[u] += fs[v];
}
}
}
// cerr<<"cnt = ";pv(cnt,cnt+V);
// cerr<<"fs = ";pv(fs,fs+V);
string ans;
int tail[A + 1] = {};
int k = K;
for (int u = 0; ; ) {
k -= cnt[u];
for (int a = A; --a >= 0; ) {
const int v = nxt[u][a];
tail[a] = ((~v && fs[v]) ? 1 : 0) + tail[a + 1];
}
if (tail[0] >= k) {
break;
}
int sumF = 0;
for (int a = 0; a < A; ++a) {
const int v = nxt[u][a];
if (~v) {
if (sumF + fs[v] + tail[a + 1] >= k) {
// cerr<<"? "<<ans<<" "<<k<<"; "<<u<<" "<<sumF<<" "<<fs[v]<<" "<<tail[a+1]<<endl;
ans += (char)('a' + a);
k -= sumF;
k -= tail[a + 1];
u = v;
goto found;
}
sumF += fs[v];
}
}
// cerr<<"HELP ans = "<<ans<<", k = "<<k<<endl;
assert(false);
found:{}
}
if (ans.empty()) {
ans = "EMPTY";
}
puts(ans.c_str());
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5704kb
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: 30ms
memory: 5536kb
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: 26ms
memory: 3624kb
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: 40ms
memory: 3468kb
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: 34ms
memory: 82604kb
input:
1 898 840 fdefauodwerznqpzszernrspbndmdfkjrbazmworfvlfbxwcprhxenouzxirrhqtwgiwdcejexotjetwgzqlqtndynfzwmfakfeojtxwrvekebmudrouskcgpzncnsxwajwaoclvqnaycgaaktqctsmbnosbajzryxpxzxuwnzpvmyfobgogbllqyxplageeufjjnrlhairtetyridmhthpplivokbinfmblugrzkcyxuhewtyoxkfzmyhgsbafmgqazoqollibsxlprjneeqursjuomypstme...
output:
y
result:
ok single line: 'y'
Test #6:
score: 0
Accepted
time: 30ms
memory: 3532kb
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: 57ms
memory: 113092kb
input:
1 10 8 tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvju...
output:
tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvjupdzdlne...
result:
ok single line: 'tahlarajyplchghlbufhsanuvbmsaf...zlcmnrtuhonflpulivygwfecgknnhvx'
Test #8:
score: 0
Accepted
time: 31ms
memory: 81752kb
input:
1 10 3 fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpf...
output:
fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpfaxlmbsj...
result:
ok single line: 'fbggdpqikbolemnowgfpwwouvbmhhx...wwjgvkuxmlyqdleytyumnytyslycfmz'
Test #9:
score: 0
Accepted
time: 37ms
memory: 60396kb
input:
1 100 64 bqrjaovelwrainyujustjcnoyqpyeuqtpwbgafxsdcmjqbgbrqkzbwejfhxswzqjjibagmdkasztqqhxsubyliuwzetglnccigmzrhxrmrrptvywyavwpkqqsyhyuhdtstkqzlqbzvpacuevwrpinfzubzjgj bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmq...
output:
bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmqqahhykfsawtiatqczizqtmabdxqotpzhufebenhmnmbkavtbaqkpjloblntpbjhazyjtkakpeydymjnhgfsojzzucjvehkuvnefhkytpaasskzteisyylpukgkerhneqjqjkkqkigljadrneojmeyebyissomxlopckhtqz...
result:
ok single line: 'bqrjaovelwrainyujustjcnoyqpyeu...ulctwnloovccolzzlgjbonxkmtsflyq'
Test #10:
score: 0
Accepted
time: 44ms
memory: 61544kb
input:
1 1000 655 xrivmcvikmllrgissoqginwxkoqyxywrvspoagwvuycscxxldlmrszeuiiqzbcvkyvcogtqagprfubjza xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtygqrtviddhsqzpxauobucvondytzflgphhqgxkyaoihvvrqrvkbbleyn...
output:
xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtwiulbxpgqmqazceacggpluxdaxnjcrvcfxzthnkvjegomnbsmbfksetqxuxukwooizgrmgupxlnspeovfiuqyndkkgrzjwxxvpjopmjhknuavonvknpcxwlcjnvrdrvvqxinzktygkkjdhdoewkwx...
result:
ok single line: 'xrivmcvikmllrgissoqginwxkoqyxw...vsirnpcffpggcsscctonqrzhktybdfd'
Test #11:
score: 0
Accepted
time: 32ms
memory: 47576kb
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: 56ms
memory: 113212kb
input:
1 15 3 accbbabccbbbaacaaabaacbacccbabaacbcbbaacbcabcbcabbbaabbbacaccbcacacbacbbbccbacaaabbaacbacbaacbcbbaaccbcbccbaabcbaacaccbbbccbbbccccbbcacacabaabccacccbcabacbbbbacbcaaababbbaacaababccbcacabcbaacccaaabbbcbcbcaaacabaacaabacbcbbccaabaccbbcbabcbcbabaabbbbabbcaacacbbcbabbabccabcbbbcbbbbcbaabcbcbacaba...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #13:
score: 0
Accepted
time: 25ms
memory: 11332kb
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: 45ms
memory: 91612kb
input:
1 8 2 aljyvnpjccrahfrixfoayvhxhwovfhsrjubibgwlxyhoryqxqlqbbpmszyogtslzmddmwkzwhjvnazabmzqeridgsukgosptmmbemzdfaezqiqedslcjkrlhjikiyzymeulnzxpnhhpbqnbdoqybnsbhesbgqbwfwyuggfnmeiceupezyjtzxhfspwrxnynxbeizewzejejkdfenecqhymgrvdgehzvahevwasmuboqwvblgbahyykskhiqtegqqylhknpbxxspyupyjufonsatqroxunkzenqoagq...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #15:
score: 0
Accepted
time: 44ms
memory: 106520kb
input:
1 10 5 badcbbacebabaaaaedeebfddecfcdfaccdeccdaffeaddafebdbedacabebbdacffdfeefebaabcbcafafbedacfbcadacfbeabafbeafdeacbdcfafcdfbbacbcbcbedecaedffceeccdfccdebaeeabfccbfdbebacfcebcebfafcfefaddfcacadccdfcfcefebbecdebadabffffecfcdababaddeeddfeccbbffdfabddaedeebcacbadbaadfaebaaaeecadfadbdadcdbdbbcbbfdeacdf...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #16:
score: 0
Accepted
time: 36ms
memory: 80540kb
input:
1 1005 796 fcfacbaaedfebebafefcaddfcbdeaeadcefdcebaabefbcfcaeddeebabaacbabdadaacfdaafdeebccfcbbffbecebfaaebdbbbbfcdadacfdababacaaacfdfcbdfeefeffbffadffcbbedfebdeefdeeeedcebeaecdbccdecdaefcfaccbabcaebdddffefeedeeafebaceafcdbadeaddcdfeaddafaaeccddbadefadafeebeccbfbceffaaddfbbbacfdacbeadcbeedcdfbecdfab...
output:
fbdfcffefdfefdabbbaaabbbdadbaecbbbfdaeaaefadaaeaacdaeecacfeccccddbedfdacaacdbdcdcaacecbbaabdccadfafdbdbdadbebfaafaeaaaacdecefdecefccacedeabcceabcfbcdeefbcabeddaeedbdaedacbeebaccbefddcdfcbaeaddfdfadadfadcbebccfbbbdbadcecfaceeefcfaebdedebdefdfaeefcedcffaeebcecbffacdcfcefefadaafbfdbadecefbfbfdceebbfcaff
result:
ok single line: 'fbdfcffefdfefdabbbaaabbbdadbae...fadaafbfdbadecefbfbfdceebbfcaff'
Test #17:
score: 0
Accepted
time: 32ms
memory: 80660kb
input:
1 1005 23 ecdafdebadceaebcadfaddbadfcbffbfaafdefecbfbceefaeeccabdaefefddfdccbcbeaeeefdedbadfcacedfabefeabcfdfcfadddadfeeeefcfeedcdcffeaedaffcdabecaecacaebddeaabcaabcebffeecafccdadacbbecbefedeefbebddcbadfdffdfabacddcdefeebddaddfdebafeffdeecaaedafebaceedfacadcdfcbdeafaaeeefcedcfdebfcbaddbdaefceaeafdca...
output:
adbcdacebaebdabbecbfdaebffefcfeaeafdaefefcffcbeeafaeebcfeddfaaaeecbabdbebeeaffebaebbfeeeafbfbfcacbdabbcafcecadbdcdccdddabaeeaacbcdfcbddbccdcaeaeeedcfefacddcbffcefbedabddddfaaffabffcbdbeafaceaaaadabeebbdedcbcbaceffcfdcfafbaeedaabcfabecfecacecdffccbaefabebceedcaadabcfbdbaeabfdccbbbeacefedbbcfbedfddbefae
result:
ok single line: 'adbcdacebaebdabbecbfdaebffefcf...abfdccbbbeacefedbbcfbedfddbefae'
Test #18:
score: 0
Accepted
time: 47ms
memory: 60884kb
input:
1 7 2 bebadebdcebccacabcabeebeebddebcaeceeebeeeadcaccecbccbeecbacbabbedcebdecebaacbedecdbdadcdbeacbabacbdaccbeacaaedeecbadecdabcaaeeecceebeaddbedeeeedbabbdebeddaabcaeeeaeeaeedcbbbbbdabbbdebaaaedaedcbabdceadcdbaaabdecdeabcbbdcbdaceacaddabbedbcadaeaeeedaaedcbeeebebcbceabecdbbcebadadcecddbbdeecbcdbedbb...
output:
EMPTY
result:
ok single line: 'EMPTY'