QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#368009#6635. Strange KeyboardMridulAhiWA 52ms426712kbC++233.6kb2024-03-26 18:20:152024-03-26 18:20:17

Judging History

你现在查看的是最新测评结果

  • [2024-03-26 18:20:17]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:426712kb
  • [2024-03-26 18:20:15]
  • 提交

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'