Submission #732908

#	Time	Username	Problem	Language	Result	Execution time	Memory
732908		vjudge1	Nivelle (COCI20_nivelle)	C++17	110 / 110	160 ms	1944 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pr pair
#define vct vector
#define ins insert
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define sz(x) ((int)(x.size()))

int comp_fraction(pr<ll, ll> f1, pr<ll, ll> f2){
	if (f1.fir*f2.sec <= f2.fir*f1.sec) return 1;
	else return 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;

	char tmpa[n];
	for (int i = 0; i < n; i++) cin >> tmpa[i];

	int a[n];
	for (int i = 0; i < n; i++) a[i] = tmpa[i] - 'a';

	vct<int> pos[26];
	for (int i = 0; i < n; i++) pos[a[i]].pb(i);

	int cnt[n];
	set<int> st;
	for (int i = n-1; i >= 0; i--){
		st.insert(a[i]);
		cnt[i] = sz(st);
	}

	pr<ll, ll> ans_fraction = mp(0, 0);
	pr<ll, ll> ans = mp(0, 0);

	for (int i = 0; i < n; i++){
		vct<int> vect = {n};
		for (int j = 0; j < 26; j++){
			if (j == a[i] || sz(pos[j]) == 0) continue;

			int ind = upper_bound(pos[j].begin(), pos[j].end(), i) - pos[j].begin();
			if (ind < sz(pos[j])) vect.pb(pos[j][ind]);
		}
		sort(vect.begin(), vect.end(), greater<int>());

		for (int j = 0; j < sz(vect); j++){
			pr<ll, ll> curr_fraction(cnt[i] - j, vect[j] - i);

			if (comp_fraction(curr_fraction, ans_fraction)){
				ans_fraction = curr_fraction;
				ans.fir = i; ans.sec = vect[j] - 1;
			}
		}
	}

	cout << ans.fir + 1 << ' ' << ans.sec + 1 << endl;



}

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