QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #416425 | #6516. New but Nostalgic Problem | E7k | WA | 66ms | 10004kb | C++20 | 1.5kb | 2024-05-21 20:30:36 | 2024-05-21 20:30:36 |
Judging History
answer
#include <bits/stdc++.h>
#define el '\n'
//#define int long long
const int N = 1e6 + 10;
using namespace std;
int idx;
bool st;
int f[N][30];
int cnt[N];
bitset<N> vis;
void fun(string &s)
{
int now = 0;
if(!vis[now])
{
memset(f[now],0,sizeof f[now]);
cnt[now] = 0;
}
vis[now] = 1;
for(int i = 0;i < s.size();i ++)
{
int y = int(s[i] - 'a');
if(f[now][y] > 0) now = f[now][y];
else
{
f[now][y] = ++ idx;
now = f[now][y];
}
if(!vis[now])
{
memset(f[now],0,sizeof f[now]);
cnt[now] = 0;
vis[now] = 1;
}
cnt[now] ++;
}
}
void dfs(int u,int k,int &id)
{
int x = 0;
for(int i = 0;i < 30;i ++)
{
if(f[u][i] > 0) x ++;
}
if(x >= k)
{
st = 1;
return ;
}
int res = 0;
for(int i = 0;i < 30;i ++)
{
if(f[u][i]) x --;
// res + x
// cnt[f[u][i]] + res + x >= k
if(cnt[f[u][i]] >= k - res - x)
{
// ans[++id] = char(i + 'a');
cout << char(i + 'a');
++ id;
dfs(f[u][i],k - res - x,id);
break;
}
res += cnt[f[u][i]];
if(st) return;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t --)
{
st = 0;
idx = 0;
int n,k;
cin >> n >> k;
vector<string> s(n + 1);
for(int i = 1;i <= n;i ++) cin >> s[i];
for(int i = 1;i <= n;i ++) fun(s[i]);
int id = 0;
dfs(0,k,id);
if(id == 0) cout << "EMPTY\n";
else cout << el;
// memset(f,0,sizeof f);
// memset(cnt,0,sizeof cnt);
vis.reset();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5848kb
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: 55ms
memory: 5756kb
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: 14ms
memory: 10004kb
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: 66ms
memory: 5816kb
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'