Submission #202364

#TimeUsernameProblemLanguageResultExecution timeMemory
202364EmmanuelACNivelle (COCI20_nivelle)C++14
0 / 110
1073 ms12540 KiB
#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-1<=alf; 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( ini , 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; }
#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...