63002023-11-14 17:23:58aballaForgó rulettkerékcpp17Hibás válasz 0/1001.582s27888 KiB
#include <bits/stdc++.h>

int n, m;
std::vector<int> a = {}, b = {};

std::string tagid2(std::string str) {
    a = {};
    int i = 0, c;
    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++;
    }

    c = 0;
    while((a.size() > 1) && (c <= str.size())) {

        b = {};
        min = str2[a[0]+1];
        i = 0;
        for(auto x : a) {
            if (str2[x+1] < min) {
                b = {x};
                min = str2[x+1];
            } 
            else if (str2[x+1] == min) {
                b.push_back(x);
            }
            i++;
        }
        a = b;
        c++;
    }
    return std::string(&str2[a[0]], &str2[a[0]+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
1Elfogadva3ms1892 KiB
2Elfogadva3ms2088 KiB
subtask20/20
3Hibás válasz3ms2300 KiB
4Hibás válasz3ms2516 KiB
5Hibás válasz3ms2624 KiB
6Hibás válasz4ms2876 KiB
7Hibás válasz4ms2732 KiB
8Hibás válasz4ms2792 KiB
9Hibás válasz4ms3108 KiB
subtask30/15
10Hibás válasz409ms4688 KiB
11Hibás válasz578ms4820 KiB
12Hibás válasz513ms4960 KiB
13Hibás válasz395ms4976 KiB
14Hibás válasz527ms4908 KiB
15Hibás válasz483ms5224 KiB
16Elfogadva493ms5176 KiB
17Hibás válasz455ms5404 KiB
subtask40/65
18Hibás válasz483ms7584 KiB
19Hibás válasz395ms8588 KiB
20Időlimit túllépés1.562s3676 KiB
21Időlimit túllépés1.554s3892 KiB
22Hibás válasz800ms8108 KiB
23Időlimit túllépés1.544s3496 KiB
24Hibás válasz717ms8488 KiB
25Időlimit túllépés1.56s3668 KiB
26Hibás válasz71ms20912 KiB
27Hibás válasz145ms11276 KiB
28Időlimit túllépés1.582s7096 KiB
29Hibás válasz71ms21516 KiB
30Hibás válasz87ms27888 KiB