6296 | 2023-11-13 17:46:08 | aballa | Forgó rulettkerék | cpp17 | Wrong answer 0/100 | 1.616s | 12136 KiB |
#include <bits/stdc++.h>
int n, m;
std::vector<int> a = {}, b = {};
std::string tagid2(std::string str) {
a = {};
int i = 0;
char min = str[0];
std::string str2 = str + str;
for(auto x : str) {
if (x < min) {
a = {i};
min = x;
} else if (x == min) {
a.push_back(i);
}
i++;
}
while(a.size() > 1) {
b = {};
min = str[a[0]+1];
i = 0;
for(auto x : a) {
if (str[x+1] < min) {
b = {i};
min = str[x+1];
}
else if (str[x+1] == min) {
b.push_back(i);
}
i++;
}
a = b;
}
return std::string(&str2[a[0]], &str2[a[0]+m]);
}
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 | 1824 KiB | ||||
2 | Wrong answer | 3ms | 2336 KiB | ||||
subtask2 | 0/20 | ||||||
3 | Wrong answer | 3ms | 2296 KiB | ||||
4 | Time limit exceeded | 1.6s | 2316 KiB | ||||
5 | Time limit exceeded | 1.549s | 1808 KiB | ||||
6 | Time limit exceeded | 1.562s | 2612 KiB | ||||
7 | Time limit exceeded | 1.562s | 2600 KiB | ||||
8 | Time limit exceeded | 1.565s | 2608 KiB | ||||
9 | Time limit exceeded | 1.616s | 2024 KiB | ||||
subtask3 | 0/15 | ||||||
10 | Time limit exceeded | 1.585s | 2384 KiB | ||||
11 | Time limit exceeded | 1.593s | 3192 KiB | ||||
12 | Time limit exceeded | 1.55s | 2524 KiB | ||||
13 | Time limit exceeded | 1.557s | 2800 KiB | ||||
14 | Time limit exceeded | 1.598s | 2996 KiB | ||||
15 | Time limit exceeded | 1.577s | 3824 KiB | ||||
16 | Time limit exceeded | 1.549s | 3104 KiB | ||||
17 | Time limit exceeded | 1.57s | 4036 KiB | ||||
subtask4 | 0/65 | ||||||
18 | Time limit exceeded | 1.562s | 3952 KiB | ||||
19 | Time limit exceeded | 1.57s | 4044 KiB | ||||
20 | Time limit exceeded | 1.562s | 3668 KiB | ||||
21 | Time limit exceeded | 1.572s | 4332 KiB | ||||
22 | Time limit exceeded | 1.557s | 4268 KiB | ||||
23 | Time limit exceeded | 1.557s | 4344 KiB | ||||
24 | Time limit exceeded | 1.582s | 3520 KiB | ||||
25 | Wrong answer | 13ms | 8552 KiB | ||||
26 | Time limit exceeded | 1.597s | 4452 KiB | ||||
27 | Time limit exceeded | 1.554s | 4392 KiB | ||||
28 | Wrong answer | 14ms | 12136 KiB | ||||
29 | Time limit exceeded | 1.598s | 3776 KiB | ||||
30 | Time limit exceeded | 1.565s | 4380 KiB |