QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#368009 | #6635. Strange Keyboard | MridulAhi | WA | 52ms | 426712kb | C++23 | 3.6kb | 2024-03-26 18:20:15 | 2024-03-26 18:20:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)((x).size())
#define all(x) begin(x), end(x)
typedef long long ll;
const ll inf = 1e16;
struct node {
int nex[26];
ll req = inf;
};
node nodes[(int)2e6];
int cur = 0;
signed main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
int _;
cin >> _;
while (_--) {
for (int i = 0; i < 1; i++) {
fill(nodes[i].nex, nodes[i].nex + 26, 0);
nodes[i].req = inf;
}
cur = 1;
int n, k;
cin >> n >> k;
string s[n];
string t;
for (int i = 0; i < n; i++) cin >> s[i];
cin >> t;
ll mn[k];
fill(mn, mn + k, inf);
mn[0] = 0;
for (auto st : s) mn[sz(st) % k] = min(mn[sz(st) % k], (ll)st.size() / k);
set<int> ns;
for (auto st : s) ns.insert(sz(st) % k);
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
pq.push({0, 0});
bool vis[k] = {0};
while (sz(pq)) {
auto [req, x] = pq.top();
pq.pop();
if (vis[x]) continue;
vis[x] = 1;
for (auto u : ns) {
int rq = mn[x] + mn[u];
int nex = x + u;
if (nex >= k) nex -= k, rq++;
if (mn[nex] > rq) {
mn[nex] = rq;
pq.push({mn[nex], nex});
}
}
}
for (int i = 1; i < k; i++) if (mn[i] < inf) mn[i]++;
for (auto st : s) {
int curn = 0;
int len = 0;
for (auto c : st) {
int x = (int)c - 'a';
int nex = nodes[curn].nex[x];
if (nex == 0) {
nodes[curn].nex[x] = cur++;
fill(nodes[cur - 1].nex, nodes[cur - 1].nex + 26, 0);
}
curn = nodes[curn].nex[x];
len++;
if (mn[(sz(st) - len) % k] < inf) nodes[curn].req = min(nodes[curn].req, mn[(sz(st) - len) % k] + 1 + (sz(st) - len) / k);
}
}
int m = sz(t);
ll ans[m + 1];
fill(ans, ans + m + 1, inf);
ans[0] = 0;
for (int i = 0; i < m; i++) {
int curn = 0;
if (ans[i] == inf) continue;
for (int j = i; j < m; j++) {
int x = (int)t[j] - 'a';
if (nodes[curn].nex[x] == 0) break;
curn = nodes[curn].nex[x];
ans[j + 1] = min(ans[j + 1], ans[i] + nodes[curn].req);
}
}
if (ans[m] >= inf) cout << -1 << "\n";
else cout << ans[m] << "\n";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 11ms
memory: 425372kb
input:
2 2 3 defgh abc abcde 1 1 a b
output:
3 -1
result:
ok 2 number(s): "3 -1"
Test #2:
score: 0
Accepted
time: 19ms
memory: 426712kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 20ms
memory: 425728kb
input:
10 446 4905 afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica afigcjhcgagabbiccehjcjajigghgbj...
output:
3 2 2 11 6 5 1 1 1 1
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 15ms
memory: 425416kb
input:
100 140 4879 baabaababbababbaabababaaababbbabbbbbbabbababbbabbbbabbbbbbaabbbbbbbbabaabbbaabaabbbaabbabaabaabbbabbbababbbaabbabaaaaabbaaabbbabb baa baabaababbababbaabababaaababbbabbbbbbabbab baabaababbababbaabababaaabab baabaababbababbaabababaaababbbabbb baabaababbababbaabababaaababbbabbbbbbabbababbb...
output:
1 1 1 1 3 1 1 1 1 1 1 3 2 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 4 3 2 1 2 1 1 1 1 1 2 1 1 1 3 1 1 1 2 1 1 1 2 3 1 1 1 2 1 1 1 1 1 1 1 1 3 2 3 1 3 1 1 2 1 2 3 2 1 1 1 3 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 4 1
result:
ok 100 numbers
Test #5:
score: -100
Wrong Answer
time: 52ms
memory: 426660kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
135
result:
wrong answer 1st numbers differ - expected: '205', found: '135'