Submission #544153

#	Time	Username	Problem	Language	Result	Execution time	Memory
544153		AlperenT	Nivelle (COCI20_nivelle)	C++17	110 / 110	55 ms	10776 KiB

nivelle

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, INF = 1e9 + 5;

int n, nxt[N][26], ansl = 1, ansr = 1;

string str;

long double ans = 1;

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

    cin >> n;

    cin >> str;

    str = '$' + str;

    fill(nxt[n + 1], nxt[n + 1] + 26, INF);

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

        nxt[i][str[i] - 'a'] = i;
    }

    for(int i = 1; i <= n; i++){
        sort(nxt[i], nxt[i] + 26);

        for(int j = 1; j < 26; j++){
            if((long double)j / (min(nxt[i][j], n + 1) - i) < ans){
                ans = (long double)j / (min(nxt[i][j], n + 1) - i);
                ansl = i, ansr = min(nxt[i][j], n + 1) - 1;
            }
        }

        if((long double)26 / (n - i + 1) < ans){
            ans = (long double)26 / (n - i + 1);
            ansl = i, ansr = n;
        }
    }

    cout << ansl << " " << ansr << "\n";
}

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