Submission #1282023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282023		Sam_a17	Nivelle (COCI20_nivelle)	C++17	110 / 110	55 ms	21772 KiB

nivelle

#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#define ll long long
using namespace std;
long long a[100006], nxt[100006][26];

int main()
{
    ll n, i, j;
    cin >> n;
    string s;
    cin >> s;
    ll l, r, cnt;
    double ans = 1;
    for (i = 0; i < n; i++)
    {
        a[i] = s[i] - 'a';
    }

    for (j = 0; j < 26; j++)
    {
        nxt[n][j] = n + 1;
    }
    for (i = n - 1; i >= 0; i--)
    {
        for (j = 0; j < 26; j++)
        {
            nxt[i][j] = nxt[i + 1][j];
        }
        nxt[i][a[i]] = i;
    }
    for (i = 0; i < n; i++)
    {
        cnt = 0;
        vector<ll> v;
        for (j = 0; j < 26; j++)
        {
            v.push_back(nxt[i][j]);
        }
        sort(v.begin(), v.end());
        j = 1;
        while (j < 26)
        {
            if (v[j] == n + 1)
            {
                break;
            }
            cnt++;
            if (ans > (double)cnt / (v[j] - i))
            {
                ans = (double)cnt / (v[j] - i);
                l = i, r = v[j] - 1;
            }
            j++;
        }

        cnt++;
        if (ans > (double)cnt / (n - i))
        {
            ans = (double)cnt / (n - i);
            l = i, r = n - 1;
        }
    }
    cout << l + 1 << " " << r + 1;
}

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