oj.uz

Submission #202364

# Submission time Handle Problem Language Result Execution time Memory
202364 2020-02-15T19:01:01 Z EmmanuelAC Nivelle (COCI20_nivelle) C++14
0 / 110
 1000 ms 12540 KB 
#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;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 12540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 342 ms 12516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 12412 KB Time limit exceeded
2 Halted 0 ms 0 KB -