Submission #849736

#	Time	Username	Problem	Language	Result	Execution time	Memory
849736		efedmrlr	Nivelle (COCI20_nivelle)	C++17	110 / 110	26 ms	752 KiB

nivelle

#include <bits/stdc++.h>
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)



using namespace std;

const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 1e6+5;
int n,m,q;
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

}
string s;
int cnt[26];
int num = 0;
vector<int> ans(27);
vector<array<int,2> > ansr(27);
void solve() {
    cin>>n;
    cin>>s;
    for(int i = 0; i<26; i++) cnt[i] = 0;
    for(int k = 1; k<=26; k++) {
        int i = 0, j = 0;
        int num = 0;
        for(int i = 0; i<26; i++) cnt[i] = 0;
        while(j < n) {
            //cout<<"j:"<<j<<"\n";

            cnt[s[j] - 'a']++;
            assert(i <= j);

            if(cnt[s[j] - 'a'] == 1) {
                num++;
            }
            while(num > k) {
                //cout<<"i:"<<i<<"\n";    
                cnt[s[i] - 'a']--;
                if(cnt[s[i] - 'a'] == 0) {
                    num--;
                }
                i++;
                
            }
            assert(num <= k);

            if(j - i + 1 > ans[k]) {
                ans[k] = j - i + 1;
                ansr[k] = {i,j};
            }
            j++;
        } 
    }
    
    long double res2 = INF;
    int l,r;
    for(int i = 1; i<=26; i++) {
        long double res = (long double) i / ans[i];

        if(res2 > res) {
            

            l = ansr[i][0];
            r = ansr[i][1];
            res2 = res;
        }
    }
    cout<<l+1<<" "<<r+1<<"\n";

}
 
signed main() {
    
    //fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Compilation message (stderr)

nivelle.cpp: In function 'void solve()':
nivelle.cpp:74:23: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     cout<<l+1<<" "<<r+1<<"\n";
      |                       ^
nivelle.cpp:74:13: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     cout<<l+1<<" "<<r+1<<"\n";
      |             ^

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