6300 2023. 11. 14 17:23:58 aballa Forgó rulettkerék cpp17 Hibás válasz 0/100 1.582s 27888 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1892 KiB
2 Elfogadva 3ms 2088 KiB
subtask2 0/20
3 Hibás válasz 3ms 2300 KiB
4 Hibás válasz 3ms 2516 KiB
5 Hibás válasz 3ms 2624 KiB
6 Hibás válasz 4ms 2876 KiB
7 Hibás válasz 4ms 2732 KiB
8 Hibás válasz 4ms 2792 KiB
9 Hibás válasz 4ms 3108 KiB
subtask3 0/15
10 Hibás válasz 409ms 4688 KiB
11 Hibás válasz 578ms 4820 KiB
12 Hibás válasz 513ms 4960 KiB
13 Hibás válasz 395ms 4976 KiB
14 Hibás válasz 527ms 4908 KiB
15 Hibás válasz 483ms 5224 KiB
16 Elfogadva 493ms 5176 KiB
17 Hibás válasz 455ms 5404 KiB
subtask4 0/65
18 Hibás válasz 483ms 7584 KiB
19 Hibás válasz 395ms 8588 KiB
20 Időlimit túllépés 1.562s 3676 KiB
21 Időlimit túllépés 1.554s 3892 KiB
22 Hibás válasz 800ms 8108 KiB
23 Időlimit túllépés 1.544s 3496 KiB
24 Hibás válasz 717ms 8488 KiB
25 Időlimit túllépés 1.56s 3668 KiB
26 Hibás válasz 71ms 20912 KiB
27 Hibás válasz 145ms 11276 KiB
28 Időlimit túllépés 1.582s 7096 KiB
29 Hibás válasz 71ms 21516 KiB
30 Hibás válasz 87ms 27888 KiB