QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #141339 | #6516. New but Nostalgic Problem | cy1999 | WA | 72ms | 5828kb | C++ | 1.4kb | 2023-08-17 10:54:46 | 2023-08-17 10:54:48 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
const int E = 26, S = 1000000;
int n, num;
struct Tr
{
int son[E + 5];
int siz;
int end;
}tr[S + 5];
int cntn = 0;
void ist(string s)
{
int len = s.size();
int p = 0;
for(int i = 0; i < len; i++)
{
if(!tr[p].son[s[i] - 'a'])
{
tr[p].son[s[i] - 'a'] = ++cntn;
}
p = tr[p].son[s[i] - 'a'];
tr[p].siz++;
if(i == len - 1)
{
tr[p].end++;
}
}
}
void init()
{
scanf("%d %d", &n, &num);
for(int i = 1; i <= n; i++)
{
string s;
cin >> s;
ist(s);
}
}
bool flag = 0;
void dfs(int u, int x)
{
if(tr[u].end)
{
return;
}
for(int i = 0; i < E; i++)
{
if(tr[u].son[i] && x)
{
x--;
}
}
if(x == 0)
{
return;
}
for(int i = 0; i < E; i++)
{
if(!tr[u].son[i])
{
continue;
}
if(x <= tr[tr[u].son[i]].siz - 1)
{
printf("%c", i + 'a');
flag = 1;
dfs(tr[u].son[i], x + 1);
return;
}
else
{
x -= tr[tr[u].son[i]].siz - 1;
}
}
}
void solve()
{
dfs(0, num);
if(!flag)
{
printf("EMPTY");
}
printf("\n");
}
void clr()
{
for(int i = 0; i <= cntn; i++)
{
tr[i].siz = tr[i].end = 0;
for(int j = 0; j < E; j++)
{
tr[i].son[j] = 0;
}
}
cntn = 0;
flag = 0;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
init();
solve();
clr();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3696kb
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: 68ms
memory: 3716kb
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: 27ms
memory: 5828kb
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: 72ms
memory: 3652kb
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'