6301 | 2023-11-15 14:31:22 | aballa | Forgó rulettkerék | cpp17 | Accepted 100/100 | 90ms | 27420 KiB |
#include <bits/stdc++.h>
int n, m;
std::vector<int> a = {}, b = {};
std::string tagid2(std::string str) {
a = {};
int c, aa;
char min = str[0], k = '{';
std::string str2 = str + str;
for(int i = 0; i < str.size(); i++) {
char x = str[i];
if (x == k) continue;
if (x < min) {
a = {i};
min = x;
} else if (x == min) {
a.push_back(i);
}
k = x;
}
c = 1;
while((a.size() > 1) && (c <= 2*str.size())) {
b = {};
min = str2[a[0]+c];
for(auto x : a) {
aa = (x+c) % str.size();
if (str2[aa] < min) {
b = {x};
min = str2[aa];
}
else if (str2[aa] == min) {
b.push_back((x)%str.size());
}
}
if (b.size() != 0) a = b;
c++;
}
return str2.substr(a[0] % str.size(), str.size());
}
std::string tagid(std::string str) {
std::string s = str + str, k, min;
min = str;
for(int i = 1; i < m; i++) {
k = std::string(&s[i], &s[i+m]);
if(min > k) min = k;
}
return min;
}
int main() {
long long count = 0, cc = 1;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::string cache;
std::vector<std::string> ids;
std::vector<int> veccount;
std::unordered_map<std::string, int> map;
std::cin >> n >> m;
for(int i = 0; i < n; i++) {
std::cin >> cache;
ids.push_back(tagid2(cache));
}
map.insert({ids[0], 0});
veccount.push_back(1);
for(int i = 1; i < n; i++) {
if (auto search = map.find(ids[i]); search != map.end()) {
veccount[search->second]++;
}
else {
map.insert({ids[i], cc});
veccount.push_back(1);
cc++;
}
}
for(const auto x : veccount) {
count += x*(x-1);
}
std::cout << count/2 << std::flush;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1896 KiB | ||||
2 | Accepted | 3ms | 2120 KiB | ||||
subtask2 | 20/20 | ||||||
3 | Accepted | 3ms | 2336 KiB | ||||
4 | Accepted | 3ms | 2548 KiB | ||||
5 | Accepted | 3ms | 2728 KiB | ||||
6 | Accepted | 3ms | 3088 KiB | ||||
7 | Accepted | 3ms | 3432 KiB | ||||
8 | Accepted | 3ms | 3632 KiB | ||||
9 | Accepted | 3ms | 3588 KiB | ||||
subtask3 | 15/15 | ||||||
10 | Accepted | 12ms | 4300 KiB | ||||
11 | Accepted | 14ms | 4464 KiB | ||||
12 | Accepted | 14ms | 4756 KiB | ||||
13 | Accepted | 12ms | 4432 KiB | ||||
14 | Accepted | 13ms | 4876 KiB | ||||
15 | Accepted | 13ms | 5436 KiB | ||||
16 | Accepted | 12ms | 5812 KiB | ||||
17 | Accepted | 13ms | 5676 KiB | ||||
subtask4 | 65/65 | ||||||
18 | Accepted | 32ms | 6448 KiB | ||||
19 | Accepted | 32ms | 6244 KiB | ||||
20 | Accepted | 30ms | 6820 KiB | ||||
21 | Accepted | 34ms | 7320 KiB | ||||
22 | Accepted | 34ms | 7136 KiB | ||||
23 | Accepted | 30ms | 6504 KiB | ||||
24 | Accepted | 32ms | 7616 KiB | ||||
25 | Accepted | 32ms | 6968 KiB | ||||
26 | Accepted | 65ms | 21448 KiB | ||||
27 | Accepted | 43ms | 9496 KiB | ||||
28 | Accepted | 28ms | 8328 KiB | ||||
29 | Accepted | 68ms | 21156 KiB | ||||
30 | Accepted | 90ms | 27420 KiB |