oj.uz

Submission #308361

# Submission time Handle Problem Language Result Execution time Memory
308361 2020-10-01T01:10:31 Z ErdosSzekeres Nivelle (COCI20_nivelle) C++14
110 / 110
 104 ms 28024 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+7;
int prox[MAXN][28], mx[28], l[28], r[28];
long double ans[28];
vector<int> v[MAXN];
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n; cin>>n;
    string s; cin>>s;

    for(char c='a'; c<='z'; c++){
        prox[n][c - 'a'] = MAXN;
        mx[c - 'a' + 1] = -1;//max length with this many characters
    }

    for(int i=n-1; i>=0; i--){
        for(char c='a'; c<='z'; c++)
            prox[i][c-'a'] = prox[i+1][c-'a'];

        prox[i][s[i]-'a'] = i;

        for(char c='a'; c<='z'; c++){
            if(prox[i][c-'a'] == MAXN)continue;
            v[i].push_back(prox[i][c-'a']);
        }
        //cout<<"Check this out: "<<i<<" "<<v[i].size()<<endl;
        sort(v[i].begin(), v[i].end());
    }
    for(int i=0; i<n; i++){
        //cout<<i<<" ---> ";
        for(int j=0; j < (int)v[i].size(); j++){
            //cout<<v[i][j]<<" ";
            int nxt = (j+1<(int)v[i].size()) ? v[i][j+1]-1 : n-1;
            if(mx[j+1] < nxt - i + 1){
                mx[j+1] = nxt - i + 1;
                l[j+1] = i;
                r[j+1] = nxt;
            }
        }
        //cout<<endl;
    }
    double tp = 1e9+7; int id;
    for(char c='a'; c<='z'; c++){
        int i = c-'a'+1; //cout<<i<<" ---> "<<mx[i]<<endl;
        //continue;
        if(mx[i] == -1)continue;
        //cout<<i<<" "<<mx[i]<<" "<<l[i]<<" "<<r[i]<<endl;
        ans[i] = ((double)i)/((double)mx[i]);
        if(ans[i] < tp){
            tp = ans[i]; id = i;
        }
    }
    //return 0;
    cout<<l[id]+1<<" "<<r[id]+1<<endl;
}

Compilation message

nivelle.cpp: In function 'int main()':
nivelle.cpp:55:29: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     cout<<l[id]+1<<" "<<r[id]+1<<endl;
      |                         ~~~~^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3200 KB Output is correct
2 Correct 5 ms 3200 KB Output is correct
3 Correct 4 ms 3200 KB Output is correct
4 Correct 4 ms 3200 KB Output is correct
5 Correct 4 ms 3124 KB Output is correct
6 Correct 5 ms 3200 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 17024 KB Output is correct
2 Correct 28 ms 17024 KB Output is correct
3 Correct 24 ms 17024 KB Output is correct
4 Correct 24 ms 17016 KB Output is correct
5 Correct 24 ms 17024 KB Output is correct
6 Correct 26 ms 17016 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 18560 KB Output is correct
2 Correct 37 ms 18552 KB Output is correct
3 Correct 39 ms 18552 KB Output is correct
4 Correct 38 ms 18552 KB Output is correct
5 Correct 37 ms 18552 KB Output is correct
6 Correct 38 ms 18552 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 27896 KB Output is correct
2 Correct 98 ms 27896 KB Output is correct
3 Correct 93 ms 27976 KB Output is correct
4 Correct 102 ms 28024 KB Output is correct
5 Correct 100 ms 28024 KB Output is correct
6 Correct 104 ms 27896 KB Output is correct