Submission #202368

#	Time	Username	Problem	Language	Result	Execution time	Memory
202368		EmmanuelAC	Nivelle (COCI20_nivelle)	C++14	110 / 110	274 ms	12536 KiB

nivelle

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;

int n,f[100010][30],alf='z'-'a',l,r,ini,fin,med;
string s;
pii a={-1,-1};

int cnt(int x,int y){
    int ans=0;
    for(int i=0; i<=alf; i++) if( f[y][i]-f[x-1][i] > 0 ) ans++;
    return ans;
}

int main()
{

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

    cin >> n >> s;

    for(int i=1; i<=n; i++){
        for(int j=0; j<=alf; j++) f[i][j] = f[i-1][j];
        f[i][ s[i-1]-'a' ]++;
    }

    int L,R;
    for(int sz=1; sz<=alf+1; sz++){

        L = R = 1;
        while( R<n ){
            if( cnt( L , n ) < sz ) break;
            while( R+1 <= n && cnt( L , R+1 ) <= sz ) R++;

            if( a.fi==-1 ) a = { sz , R-L+1 } , l = L , r = R;
            if( sz*a.se < a.fi*(R-L+1) ) a = { sz , R-L+1 } , l = L , r  = R;
            L++;
        }

    }

    cout << l << " " << r;

    return 0;
}

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