Submission #752758

#	Time	Username	Problem	Language	Result	Execution time	Memory
752758		ducanh1234	Nivelle (COCI20_nivelle)	C++17	0 / 110	1047 ms	13808 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;
// #define int long long 
template<class T> void read(T& t){ cin >> t; }
template<class T, class... H> void read(T& t, H&...h){ read(t); read(h...); }
template<class T> void read(vector<T>& t){ for(auto&x : t) read(x); }
template<class T> void write(const T t){ cout << t << ' ';}
template<class T> void print(const T t){ cout << t << '\n';}
template<class T,class...H> void print(const T& t, const H&...h){ cout << t; cout << " "; print(h...); }
template<class T> void debug(const T t) { cerr << t; } 
template<class T,class...H> void debug(const T& t, const H&...h){ 
    cerr << t; 
    if(sizeof...(h)) cerr << ", ";
    debug(h...); 
}
#define dbg(...) cerr << "LINE(" << __LINE__ << ") : [" <<  #__VA_ARGS__ << "] = [", debug(__VA_ARGS__), cerr << "]\n";  
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)    
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back 
#define vt vector
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

signed main(){
    ios::sync_with_stdio(false); cin.tie(0); srand(time(NULL));
    int n; string s; read(n, s);
    vt<vt<int>> pre(n + 1, vt<int>(26, 0));
    FOR(i, 0, n - 1){
        pre[i + 1] = pre[i]; pre[i + 1][s[i] - 'a']++;
    }
    auto check = [&](int m, int j) -> int{
        int cnt = 0;
        FOR(ii, 0, 25){
            cnt += (pre[j + 1][ii] - pre[m][ii] > 0);
        }
        return cnt;
    };
    double Max = 0;
    int left = 0, right = 0;
    FOR(i, 1, 26){
        if(i > n || (26 - count(all(pre[n]), 0LL)) < i) continue;
        FOR(j, i, n - 1){
            int l = 0, r = j, res = n;
            while(l <= r){
                int m = l + r >> 1;
                if(check(m, j) == i) res = m, r = m - 1;
                else if(check(m, j) > i) r = m - 1;
                else l = m + 1;
            }
            if((j - res + 1) * 1.0 / i > Max){
                Max = (j - res + 1) * 1.0 / i;
                left = res, right = j;
            }
        }
    }
    print(left + 1, right + 1);
    return 0;
}

// 26 * 26 * log(n) * n

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:46:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |                 int m = l + r >> 1;
      |                         ~~^~~

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