62962023-11-13 17:46:08aballaForgó rulettkerékcpp17Wrong answer 0/1001.616s12136 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1824 KiB
2Wrong answer3ms2336 KiB
subtask20/20
3Wrong answer3ms2296 KiB
4Time limit exceeded1.6s2316 KiB
5Time limit exceeded1.549s1808 KiB
6Time limit exceeded1.562s2612 KiB
7Time limit exceeded1.562s2600 KiB
8Time limit exceeded1.565s2608 KiB
9Time limit exceeded1.616s2024 KiB
subtask30/15
10Time limit exceeded1.585s2384 KiB
11Time limit exceeded1.593s3192 KiB
12Time limit exceeded1.55s2524 KiB
13Time limit exceeded1.557s2800 KiB
14Time limit exceeded1.598s2996 KiB
15Time limit exceeded1.577s3824 KiB
16Time limit exceeded1.549s3104 KiB
17Time limit exceeded1.57s4036 KiB
subtask40/65
18Time limit exceeded1.562s3952 KiB
19Time limit exceeded1.57s4044 KiB
20Time limit exceeded1.562s3668 KiB
21Time limit exceeded1.572s4332 KiB
22Time limit exceeded1.557s4268 KiB
23Time limit exceeded1.557s4344 KiB
24Time limit exceeded1.582s3520 KiB
25Wrong answer13ms8552 KiB
26Time limit exceeded1.597s4452 KiB
27Time limit exceeded1.554s4392 KiB
28Wrong answer14ms12136 KiB
29Time limit exceeded1.598s3776 KiB
30Time limit exceeded1.565s4380 KiB