Submission #308361

#	Time	Username	Problem	Language	Result	Execution time	Memory
308361		ErdosSzekeres	Nivelle (COCI20_nivelle)	C++14	110 / 110	104 ms	28024 KiB

nivelle

#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 (stderr)

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 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 48 / 48