62972023-11-13 20:00:18aballaForgó rulettkerékcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2168 KiB
2Hibás válasz3ms2276 KiB
subtask20/20
3Hibás válasz3ms2504 KiB
4Hibás válasz3ms2688 KiB
5Hibás válasz3ms2884 KiB
6Hibás válasz6ms3124 KiB
7Hibás válasz4ms3328 KiB
8Hibás válasz6ms3628 KiB
9Hibás válasz6ms3828 KiB
subtask30/15
10Hibás válasz451ms5448 KiB
11Hibás válasz625ms5628 KiB
12Hibás válasz558ms5720 KiB
13Hibás válasz432ms5296 KiB
14Hibás válasz559ms5228 KiB
15Hibás válasz550ms5616 KiB
16Hibás válasz465ms5908 KiB
17Hibás válasz490ms5876 KiB
subtask40/65
18Hibás válasz575ms8048 KiB
19Hibás válasz483ms9068 KiB
20Időlimit túllépés1.539s4196 KiB
21Időlimit túllépés1.554s4448 KiB
22Hibás válasz917ms8868 KiB
23Időlimit túllépés1.582s4520 KiB
24Hibás válasz827ms9444 KiB
25Időlimit túllépés1.565s4444 KiB
26Hibás válasz136ms21444 KiB
27Hibás válasz234ms11856 KiB
28Időlimit túllépés1.557s7240 KiB
29Hibás válasz144ms21488 KiB
30Hibás válasz134ms28064 KiB