Submission #1281659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281659		arman.khachatryan	Nivelle (COCI20_nivelle)	C++20	0 / 110	47 ms	20888 KiB

nivelle

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    ll n, i, j;
    cin>>n;
    string s;
    cin>>s;
    ll next[n][26];
    ll l, r, cnt;
    double ans=1e9;
    for(j=0; j<26; j++){
        next[n-1][j]=n;
    }
    for(i=n-2; i>=0; i--){
        for(j=0; j<26; j++){
            next[i][j]=next[i+1][j];
        }
        next[i][s[i+1]-'a']=i+1;
    }
    for(i=0; i<n; i++){
        cnt=0;
        sort(next[i], next[i]+26);
        for(j=0; j<26; j++){
            if(next[i][j]==n){
                break;
            }
            if(j==s[i]-'a'){
                continue;
            }
            cnt++;
            if(ans>(double)cnt/(next[i][j]-i)){
                ans=(double)cnt/(next[i][j]-i);
                l=i, r=next[i][j]-1;
            }
        }
        cnt++;
        if(ans>(double)cnt/(n-i)){
            ans=(double)cnt/(n-i);
            l=i+1, 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