62972023-11-13 20:00:18aballaForgó rulettkerékcpp17Wrong answer 0/1001.582s28064 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;
        std::cout << a.size() << " ";
        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
1Accepted3ms2168 KiB
2Wrong answer3ms2276 KiB
subtask20/20
3Wrong answer3ms2504 KiB
4Wrong answer3ms2688 KiB
5Wrong answer3ms2884 KiB
6Wrong answer6ms3124 KiB
7Wrong answer4ms3328 KiB
8Wrong answer6ms3628 KiB
9Wrong answer6ms3828 KiB
subtask30/15
10Wrong answer451ms5448 KiB
11Wrong answer625ms5628 KiB
12Wrong answer558ms5720 KiB
13Wrong answer432ms5296 KiB
14Wrong answer559ms5228 KiB
15Wrong answer550ms5616 KiB
16Wrong answer465ms5908 KiB
17Wrong answer490ms5876 KiB
subtask40/65
18Wrong answer575ms8048 KiB
19Wrong answer483ms9068 KiB
20Time limit exceeded1.539s4196 KiB
21Time limit exceeded1.554s4448 KiB
22Wrong answer917ms8868 KiB
23Time limit exceeded1.582s4520 KiB
24Wrong answer827ms9444 KiB
25Time limit exceeded1.565s4444 KiB
26Wrong answer136ms21444 KiB
27Wrong answer234ms11856 KiB
28Time limit exceeded1.557s7240 KiB
29Wrong answer144ms21488 KiB
30Wrong answer134ms28064 KiB