Submission #844557

#	Time	Username	Problem	Language	Result	Execution time	Memory
844557		vjudge1	Nivelle (COCI20_nivelle)	C++17	37 / 110	1051 ms	11348 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 5, MOD = 1e9 + 7;

int arr[N][26];
map<char, int> mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    string str;

    cin >> n >> str;

    str = "#" + str;
    bool ok = true;

    for(int i = 1; i <= n; i++)
    {
        arr[i][str[i] - 'a']++;
        mp[str[i]]++;

        if(str[i] != 'a' and str[i] != 'b')
            ok = false;
    }

    if(ok)
    {
        int cnt = 1, left = 1, right = n;

        long double ans = (long double)2 / (long double)n;

        for(int i = 1; i <= n; i++)
        {
            if(str[i] != str[i - 1])
            {
                cnt = 1;
                if((long double)1 / (long double)cnt < ans)
                {
                    ans = (long double)1 / (long double)cnt;
                    left = i, right = i;
                }

            }
            else
            {
                cnt++;
                if((long double)1 / (long double)cnt < ans)
                {
                    ans = (long double)1 / (long double)cnt;
                    left = i - cnt + 1, right = i;
                }
            }
        }

        cout << left << " " << right << '\n';
        return 0;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < 26; j++)
        {
            arr[i][j] += arr[i - 1][j];
        }
    }

    int left = 1, right = 1;
    long double ans = 1;

    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            int cnt = 0;

            for(int k = 0; k < 26; k++)
            {
                if(arr[j][k] - arr[i - 1][k])
                {
                    cnt++;
                }
            }
            long double l = j - i + 1;

            if((long double)cnt / l < ans)
            {
                ans = (long double)cnt / l;
                left = i, right = j;
            }
        }
    }

    cout << left << " " << right << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 0 / 25
• Subtask 5: 0 / 48