63012023-11-15 14:31:22aballaForgó rulettkerékcpp17Elfogadva 100/10090ms27420 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1896 KiB
2Elfogadva3ms2120 KiB
subtask220/20
3Elfogadva3ms2336 KiB
4Elfogadva3ms2548 KiB
5Elfogadva3ms2728 KiB
6Elfogadva3ms3088 KiB
7Elfogadva3ms3432 KiB
8Elfogadva3ms3632 KiB
9Elfogadva3ms3588 KiB
subtask315/15
10Elfogadva12ms4300 KiB
11Elfogadva14ms4464 KiB
12Elfogadva14ms4756 KiB
13Elfogadva12ms4432 KiB
14Elfogadva13ms4876 KiB
15Elfogadva13ms5436 KiB
16Elfogadva12ms5812 KiB
17Elfogadva13ms5676 KiB
subtask465/65
18Elfogadva32ms6448 KiB
19Elfogadva32ms6244 KiB
20Elfogadva30ms6820 KiB
21Elfogadva34ms7320 KiB
22Elfogadva34ms7136 KiB
23Elfogadva30ms6504 KiB
24Elfogadva32ms7616 KiB
25Elfogadva32ms6968 KiB
26Elfogadva65ms21448 KiB
27Elfogadva43ms9496 KiB
28Elfogadva28ms8328 KiB
29Elfogadva68ms21156 KiB
30Elfogadva90ms27420 KiB