6301 2023. 11. 15 14:31:22 aballa Forgó rulettkerék cpp17 Elfogadva 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1896 KiB
2 Elfogadva 3ms 2120 KiB
subtask2 20/20
3 Elfogadva 3ms 2336 KiB
4 Elfogadva 3ms 2548 KiB
5 Elfogadva 3ms 2728 KiB
6 Elfogadva 3ms 3088 KiB
7 Elfogadva 3ms 3432 KiB
8 Elfogadva 3ms 3632 KiB
9 Elfogadva 3ms 3588 KiB
subtask3 15/15
10 Elfogadva 12ms 4300 KiB
11 Elfogadva 14ms 4464 KiB
12 Elfogadva 14ms 4756 KiB
13 Elfogadva 12ms 4432 KiB
14 Elfogadva 13ms 4876 KiB
15 Elfogadva 13ms 5436 KiB
16 Elfogadva 12ms 5812 KiB
17 Elfogadva 13ms 5676 KiB
subtask4 65/65
18 Elfogadva 32ms 6448 KiB
19 Elfogadva 32ms 6244 KiB
20 Elfogadva 30ms 6820 KiB
21 Elfogadva 34ms 7320 KiB
22 Elfogadva 34ms 7136 KiB
23 Elfogadva 30ms 6504 KiB
24 Elfogadva 32ms 7616 KiB
25 Elfogadva 32ms 6968 KiB
26 Elfogadva 65ms 21448 KiB
27 Elfogadva 43ms 9496 KiB
28 Elfogadva 28ms 8328 KiB
29 Elfogadva 68ms 21156 KiB
30 Elfogadva 90ms 27420 KiB