Submission #851641

#	Time	Username	Problem	Language	Result	Execution time	Memory
851641		NotLinux	Nivelle (COCI20_nivelle)	C++17	110 / 110	519 ms	11308 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
void solve(){
	int n;cin >> n;
	string inp;cin >> inp;
	int cnt[n+1][26],arr[n+1];
	memset(cnt , 0 , sizeof(cnt));

	function < int (int , int) >  eval = [&](int l , int r){//1 indexli
		int res = 0;
		for(int k = 0;k<26;k++)res += (cnt[r][k] - cnt[l-1][k]) > 0;
		return res;
	};

	for(int i = 1;i<=n;i++){
		char ch = inp[i-1];
		arr[i] = ch - 'a';
		cnt[i][arr[i]]++;
		for(int j = 0;j<26;j++){
			cnt[i][j] += cnt[i-1][j];
		}
	}
	int pay = 2*n , payda = 1 , ansl = 1 , ansr = 1;
	for(int i = 1;i<=n;i++){
		int mx = eval(i,n);
		for(int j = 1;j<=mx;j++){
			int l = i , r = n;
			while(l < r){
				int mid = (l+r)/2;
				if(eval(i,mid) > j)r = mid;
				else l = mid+1;
			}
			if(eval(i,l) > j)l--;
			int len = l - i + 1 , realdiff = eval(i,l);
			if(pay * len > realdiff * payda){
				pay = realdiff;
				payda = len;
				ansl = i;
				ansr = l;
			}
			//if(i == 1)cout << i << " " << l << " " << realdiff << " " << j <<  endl;
		}
	}
	cout << ansl << " " << ansr << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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