6296 2023. 11. 13 17:46:08 aballa Forgó rulettkerék cpp17 Hibás válasz 0/100 1.616s 12136 KiB
#include <bits/stdc++.h>

int n, m;
std::vector<int> a = {}, b = {};

std::string tagid2(std::string str) {
    a = {};
    int i = 0;
    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++;
    }

    while(a.size() > 1) {
        b = {};
        min = str[a[0]+1];
        i = 0;
        for(auto x : a) {
            if (str[x+1] < min) {
                b = {i};
                min = str[x+1];
            } 
            else if (str[x+1] == min) {
                b.push_back(i);
            }
            i++;
        }
        a = b;
    }
    return std::string(&str2[a[0]], &str2[a[0]+m]);
}

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 1824 KiB
2 Hibás válasz 3ms 2336 KiB
subtask2 0/20
3 Hibás válasz 3ms 2296 KiB
4 Időlimit túllépés 1.6s 2316 KiB
5 Időlimit túllépés 1.549s 1808 KiB
6 Időlimit túllépés 1.562s 2612 KiB
7 Időlimit túllépés 1.562s 2600 KiB
8 Időlimit túllépés 1.565s 2608 KiB
9 Időlimit túllépés 1.616s 2024 KiB
subtask3 0/15
10 Időlimit túllépés 1.585s 2384 KiB
11 Időlimit túllépés 1.593s 3192 KiB
12 Időlimit túllépés 1.55s 2524 KiB
13 Időlimit túllépés 1.557s 2800 KiB
14 Időlimit túllépés 1.598s 2996 KiB
15 Időlimit túllépés 1.577s 3824 KiB
16 Időlimit túllépés 1.549s 3104 KiB
17 Időlimit túllépés 1.57s 4036 KiB
subtask4 0/65
18 Időlimit túllépés 1.562s 3952 KiB
19 Időlimit túllépés 1.57s 4044 KiB
20 Időlimit túllépés 1.562s 3668 KiB
21 Időlimit túllépés 1.572s 4332 KiB
22 Időlimit túllépés 1.557s 4268 KiB
23 Időlimit túllépés 1.557s 4344 KiB
24 Időlimit túllépés 1.582s 3520 KiB
25 Hibás válasz 13ms 8552 KiB
26 Időlimit túllépés 1.597s 4452 KiB
27 Időlimit túllépés 1.554s 4392 KiB
28 Hibás válasz 14ms 12136 KiB
29 Időlimit túllépés 1.598s 3776 KiB
30 Időlimit túllépés 1.565s 4380 KiB