QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #222250 | #6516. New but Nostalgic Problem | kabuu# | WA | 27ms | 5924kb | C++20 | 1.4kb | 2023-10-21 16:26:11 | 2023-10-21 16:26:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N = 1E6 + 10;
int nxt[N][26], siz[N];
int tot;
int newNode() {
++tot;
for (int i = 0; i < 26; i++) {
nxt[tot][i] = 0;
}
siz[tot] = 0;
return tot;
}
void solve()
{
int n,k;
cin>>n>>k;
vector <string> s(n+1);
for(int i=1;i<=n;i++) cin>>s[i];
tot = 0;
newNode();
for(int i=1;i<=n;i++)
{
int p = 1;
for (int j = 0; j < s[i].size(); j++) {
siz[p]++;
if (!nxt[p][s[i][j] - 'a']) {
nxt[p][s[i][j] - 'a'] = newNode();
}
p = nxt[p][s[i][j] - 'a'];
}
siz[p]++;
}
string ans;
int p = 1;
while (true) {
vector<int> pre(27), suf(28);
for (int i = 0; i < 26; i++) {
pre[i + 1] = pre[i] + siz[nxt[p][i]];
}
for (int i = 25; i >= 0; i--) {
suf[i + 1] = suf[i + 2] + (siz[nxt[p][i]] > 0);
}
int id = -1;
for (int i = 1; i <= 26; i++) {
if (pre[i] + suf[i + 1] >= k) {
int cur = max(0, k - pre[i - 1] - suf[i + 1]);
if (cur >= 2) {
id = i - 1;
k = cur;
}
break;
}
}
if (id == -1) {
break;
}
ans += char('a' + id);
// cerr << char('a' + id) << " " << k << "\n";
p = nxt[p][id];
}
if (ans.empty()) {
cout << "EMPTY\n";
} else {
cout << ans << "\n";
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
int T;
cin>>T;
while(T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5924kb
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: 5696kb
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: 9ms
memory: 5700kb
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: 27ms
memory: 5732kb
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'