6297 2023. 11. 13 20:00:18 aballa Forgó rulettkerék cpp17 Hibás válasz 0/100 1.582s 28064 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2168 KiB
2 Hibás válasz 3ms 2276 KiB
subtask2 0/20
3 Hibás válasz 3ms 2504 KiB
4 Hibás válasz 3ms 2688 KiB
5 Hibás válasz 3ms 2884 KiB
6 Hibás válasz 6ms 3124 KiB
7 Hibás válasz 4ms 3328 KiB
8 Hibás válasz 6ms 3628 KiB
9 Hibás válasz 6ms 3828 KiB
subtask3 0/15
10 Hibás válasz 451ms 5448 KiB
11 Hibás válasz 625ms 5628 KiB
12 Hibás válasz 558ms 5720 KiB
13 Hibás válasz 432ms 5296 KiB
14 Hibás válasz 559ms 5228 KiB
15 Hibás válasz 550ms 5616 KiB
16 Hibás válasz 465ms 5908 KiB
17 Hibás válasz 490ms 5876 KiB
subtask4 0/65
18 Hibás válasz 575ms 8048 KiB
19 Hibás válasz 483ms 9068 KiB
20 Időlimit túllépés 1.539s 4196 KiB
21 Időlimit túllépés 1.554s 4448 KiB
22 Hibás válasz 917ms 8868 KiB
23 Időlimit túllépés 1.582s 4520 KiB
24 Hibás válasz 827ms 9444 KiB
25 Időlimit túllépés 1.565s 4444 KiB
26 Hibás válasz 136ms 21444 KiB
27 Hibás válasz 234ms 11856 KiB
28 Időlimit túllépés 1.557s 7240 KiB
29 Hibás válasz 144ms 21488 KiB
30 Hibás válasz 134ms 28064 KiB