Submission #478114

#	Time	Username	Problem	Language	Result	Execution time	Memory
478114		mychecksedad	Nivelle (COCI20_nivelle)	C++17	110 / 110	345 ms	71492 KiB

nivelle

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;



int n, arr[N];
string s;
vector<vector<bool>> dp(N, vector<bool>(26));
int ansx = 1, ansy = 1;
double ans = 1;
void solve(){
    cin >> n >> s;
    for(int i =0 ; i <= n; ++i) arr[i] = 0;
    for(int i = 1; i <= n; ++i){
        int cur = i;
        int poss = s[i - 1] - 'a';
        while(cur > 0 && dp[cur][poss] == 0){
            dp[cur][poss] = 1;
            ++arr[cur];
            --cur;
        }
        for(int s = 1; s <= 26; ++s){
            int l = 1, r = i;
            int pos = i;
            while(l <= r){
                int mid = (l+r)/2;
                if(arr[mid] == s){
                    pos = mid;
                    r = mid - 1;
                }else if(arr[mid] < s){
                    r = mid - 1;
                }else l = mid + 1;
            }
            if(pos <= i){
                if((double) s / double(i - pos + 1) < ans){
                    ans = (double) s / double(i - pos + 1);
                    ansx = pos;
                    ansy = i;
                }
            }
        }
    }
    cout << ansx << ' ' << ansy;
}



int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:60:16: warning: unused variable 'aa' [-Wunused-variable]
   60 |     int T = 1, aa;
      |                ^~

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