Submission #892077

#	Time	Username	Problem	Language	Result	Execution time	Memory
892077		kh0i	Nivelle (COCI20_nivelle)	C++17	110 / 110	101 ms	776 KiB

nivelle

/**
 *	author: kh0i
 *	created: 21.03.2022 14:33:34
**/
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;

int n;
string s;

void solve(){
    cin >> n;
    cin >> s;
    s = ' ' + s;
    double ans = DBL_MAX, cur;
    int ansl = 1, ansr = 1;
    unordered_map<char, int> mp;

    for(int i = 1; i <= 26; ++i){
        int l = 1, r = 1;
        mp.clear();
        while(r <= n){
            mp[s[r]]++;
            while(mp.size() > i){
                mp[s[l]]--;
                if(mp[s[l]] == 0)
                    mp.erase(s[l]);
                ++l;
            }
            if(mp.size() == i){
                cur = double(i) / double(r - l + 1);
                if(cur < ans or (cur == ans and (r - l + 1) > (ansr - ansl + 1))){
                    ans = cur;
                    ansl = l;
                    ansr = r;
                }
            }
            ++r;
        }
    }
    cout << ansl << ' ' << ansr;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
        solve();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

// Write stuff down

Compilation message (stderr)

nivelle.cpp: In function 'void solve()':
nivelle.cpp:32:29: warning: comparison of integer expressions of different signedness: 'std::unordered_map<char, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |             while(mp.size() > i){
      |                   ~~~~~~~~~~^~~
nivelle.cpp:38:26: warning: comparison of integer expressions of different signedness: 'std::unordered_map<char, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |             if(mp.size() == i){
      |                ~~~~~~~~~~^~~~

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