Submission #1132651

#TimeUsernameProblemLanguageResultExecution timeMemory
1132651DangKhoizzzzNivelle (COCI20_nivelle)C++20
110 / 110
103 ms540 KiB
#include <bits/stdc++.h>
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e6 + 7;

void minimize(array <int , 4> &a , array <int , 4> b)
{
    if(a[0] * b[1] > b[0] * a[1]) {a = b;}
}
array <int , 4> ans = {1 , 1 , 1 , 1};

vector <int> cur;

int counting()
{
    int ok = 0;
    for(int c = 0; c < 26; c++)
    {
        if(cur[c]) ok++;
    }
    return ok;
}

int n; char s[maxn];

void solve_case(int req)
{
    cur.assign(26 , 0);

    int j = 1;

    for(int i = 1; i <= n; i++)
    {
        cur[s[i] - 'a']++;
        while(counting() > req)
        {
            cur[s[j] - 'a']--; j++;
        }
        if(counting() == req)
        {
            //cout << j << ' ' << i << '\n';
            minimize(ans , (array <int , 4>){req , i - j + 1 , j , i});
        }
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];

    //solve_case(2);

    //cout << ans[2] << ' ' << ans[3] << '\n';

    //return;

    for(int i = 1; i <= 26; i++)
    {
        solve_case(i);
    }

    cout << ans[2] << ' ' << ans[3] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...