63002023-11-14 17:23:58aballaForgó rulettkerékcpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1892 KiB
2Accepted3ms2088 KiB
subtask20/20
3Wrong answer3ms2300 KiB
4Wrong answer3ms2516 KiB
5Wrong answer3ms2624 KiB
6Wrong answer4ms2876 KiB
7Wrong answer4ms2732 KiB
8Wrong answer4ms2792 KiB
9Wrong answer4ms3108 KiB
subtask30/15
10Wrong answer409ms4688 KiB
11Wrong answer578ms4820 KiB
12Wrong answer513ms4960 KiB
13Wrong answer395ms4976 KiB
14Wrong answer527ms4908 KiB
15Wrong answer483ms5224 KiB
16Accepted493ms5176 KiB
17Wrong answer455ms5404 KiB
subtask40/65
18Wrong answer483ms7584 KiB
19Wrong answer395ms8588 KiB
20Time limit exceeded1.562s3676 KiB
21Time limit exceeded1.554s3892 KiB
22Wrong answer800ms8108 KiB
23Time limit exceeded1.544s3496 KiB
24Wrong answer717ms8488 KiB
25Time limit exceeded1.56s3668 KiB
26Wrong answer71ms20912 KiB
27Wrong answer145ms11276 KiB
28Time limit exceeded1.582s7096 KiB
29Wrong answer71ms21516 KiB
30Wrong answer87ms27888 KiB