Submission #844878

#	Time	Username	Problem	Language	Result	Execution time	Memory
844878		vjudge1	Nivelle (COCI20_nivelle)	C++17	110 / 110	75 ms	840 KiB

nivelle

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #define OPEN freopen(".in", "r", stdin); \
                 freopen(".out", "w", stdout);
#else
    #define OPEN void(23);
#endif

template <typename T, size_t sz>
ostream& operator<< (ostream &out, array <T, sz> arr)
{
    for(T &i : arr) out << i << " ";
    return out;
}

void solve()
{
    int n; cin >> n;
    string str; cin >> str; str = '#' + str;

    auto f = [&](int k) -> tuple <long double, int, int>
    {
        double ans = 2;

        int l = 1, r = 1;
        array <int, 26> arr = {};

        auto check = [&]() -> bool
        {
            int cnt = 0;
            for(int i = 0; i < 26; i++) cnt += arr[i] != 0;
            //cerr << arr << "\n";

            return cnt <= k;
        };

        pair <int, int> inds;

        arr[str[l] - 'a']++;
        while(l <= n && r <= n)
        {
            if(check())
            {
                double calc = double(k) / (r - l +1);
                //cerr << k << " " << l << " " << r << "\n";
                if(calc < ans) inds = {l, r};
                ans = min(ans, calc);
                r++;
                arr[str[r] - 'a']++;
                continue;
            }
            else
            {
                arr[str[l] - 'a']--;
                l++;
            }
        }

        return tuple <long double, int, int>{ans, inds.first, inds.second};
    };

    long double ans = 2;
    pair <int, int> cevinds;
    for(int k = 1; k <= 26; k++)
    {
        auto [calc, l, r] = f(k);
        if(calc < ans) cevinds = {l, r};
        ans = min(ans, calc);
    }   

    cout << cevinds.first << " " << cevinds.second << "\n";

    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }
}

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