제출 #202365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202365		EmmanuelAC	Nivelle (COCI20_nivelle)	C++14	62 / 110	1091 ms	12568 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' ]++;
    }

    for(int sz=1; sz<=alf+1; sz++){
        for(int i=1; i<=n; i++){

            if( cnt( i , n ) < sz ) continue;
            if( cnt( i , n ) == sz ){
                if( a.fi==-1 ) a = { sz , n-i+1 } , l = i , r = n;
                if( sz*a.se < a.fi*(n-i+1) ) a = { sz , n-i+1 } , l = i , r  = n;
                continue;
            }

            ini = i;
            fin = n;
            while( ini < fin ){
                med = (ini+fin)/2;
                if( cnt( i , med ) <= sz ){
                    ini = med+1;
                }else{
                    fin = med;
                }
            }

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

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

    return 0;
}

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