QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #419046 | #6516. New but Nostalgic Problem | DaDian# | WA | 13ms | 3660kb | C++20 | 1.5kb | 2024-05-23 17:16:05 | 2024-05-23 17:16:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5+7,mod=1e9+7,INF=1e18;
#define endl '\n'
void solve(){
ll n, k;
cin >> n >> k;
vector<string> ve(n + 1);
for(ll i = 1; i <= n; i++){
string s; cin >> s;
ve[i] = s;
}
sort(ve.begin() + 1, ve.end());
auto find1 = [&](auto &&find1, ll l, ll r, ll dex, ll k1) -> string{
// cout << l << " " << r << " " << dex << " " << k1 << endl;
map<ll, ll> mp;
ll sum = 0, cnt = 1;
for(ll i = l; i <= r; i++){
if((int)ve[i].size() <= dex){
sum++;
continue;
}
mp[ve[i][dex] - 'a']++;
}
if(sum != 0){
return find1(find1, l + sum, r, dex, k1 - sum);
}
// for(auto [x, y] : mp){
// cout << x << " " << y << endl;
// }
ll num = mp.size();
if(num >= k1) return "";
for(ll i = 0; i < 26; i++){
if(mp[i] == 0) continue;
if(num - cnt + mp[i] + sum >= k1){
ll c1 = k1 - num + cnt - sum;
return (char)('a' + i) + find1(find1, l + sum, l + mp[i] - 1, dex + 1, c1);
}else{
cnt++;
sum += mp[i];
}
}
return "";
};
string s = find1(find1, 1, n, 0, k);
if(s == "") cout << "EMPTY" << endl;
else cout << s << endl;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
ll T=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
1
4 4
abcd
amxy
aser
adfg
1
4 2
abcd
amxy
aser
adfg
1
4 4
x
t
z
y
1
4 3
aaaaaaaaaaaaaaaaaaaaa
aaa
aaaaaaaaaaaaa
aaaaaaaa
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
input:
2 5 3 gdcpc gdcpcpcp suasua suas sususua 3 3 a b c
output:
gdcpc EMPTY
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 13ms
memory: 3660kb
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:
wrong answer 220th lines differ - expected: 'tr', found: 't'