Submission #1282017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282017		Sam_a17	Nivelle (COCI20_nivelle)	C++17	0 / 110	51 ms	21768 KiB

nivelle

#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#define ll long long
using namespace std;
long long a[100000], nxt[100000][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 = 0;
        while (j < 26)
        {
            if (v[j] == n + 1)
            {
                break;
            }
            if (v[j] == a[i])
            {
                j++;
                continue;
            }
            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: 0 / 7
• Subtask 2: 0 / 17
• Subtask 3: 0 / 13
• Subtask 4: 0 / 25
• Subtask 5: 0 / 48