QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #703597 | #6516. New but Nostalgic Problem | libantian# | WA | 16ms | 5924kb | C++23 | 1.7kb | 2024-11-02 18:00:53 | 2024-11-02 18:01:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
const int N=1000010;
int son[N][26],cnt[N],idx;
int n,m;string res;
void insert(string s){
int p=0;
for(int i=0;i<s.size();i++){
int u=s[i]-'a';
if(!son[p][u])son[p][u]=++idx;
p=son[p][u];
cnt[p]++;
}
}
void query(int p){
if(m<=1)return ;
int sum=0;
int pos=-1;
for(int i=0;i<26;i++){
if(son[p][i]){
if(cnt[son[p][i]])sum++;
}
}
if(sum>=m)return;
for(int i=0;i<26;i++){
if(son[p][i]){
if(cnt[son[p][i]]>=2)sum+=cnt[son[p][i]]-1,pos=i;
}
if(sum>=m)break;
}
if(pos==-1)return;
m=min(sum,m);
for(int i=pos+1;i<26;i++){
if(son[p][i])m--;
}
for(int i=0;i<pos;i++){
if(cnt[son[p][i]])m-=cnt[son[p][i]];
}
res+=(char)(pos+'a');
query(son[p][pos]);
}
int last;
void solve(){
for(int i=0;i<=last+2;i++){
cnt[i]=0;
for(int j=0;j<26;j++)son[i][j]=0;
}
idx=0;
cin>>n>>m;
res.clear();
int num=0;
last=0;
for(int i=1;i<=n;i++){
string s;
cin>>s;
last+=s.size();
insert(s);
}
query(0);
if(res.size()==0)cout<<"EMPTY"<<endl;
else cout<<res<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout << setiosflags(ios::fixed) << setprecision(15);
int T;
T=1;
cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5692kb
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: 12ms
memory: 5700kb
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: 7ms
memory: 5640kb
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: 16ms
memory: 5924kb
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 8051st lines differ - expected: 'd', found: 'di'