Submission #334055

#	Time	Username	Problem	Language	Result	Execution time	Memory
334055		ronnith	Nivelle (COCI20_nivelle)	C++14	110 / 110	89 ms	748 KiB

nivelle

#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
#define trav(a, b) for(auto a : b)
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define v vector
#define vl vector<ll>
#define mk make_pair
#define f first
#define s second

using namespace std;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	string s;
	cin >> n >> s;
	int fr[26];
	for(int i = 0;i < 26;i ++){
		fr[i] = -1;
	}
	ld an = 1;
	pair<int, int> ans = mk(1, 1);
	for(int i = n - 1;i >= 0;i --){
		fr[s[i] - 'a'] = i;
		vector<int> arr;
		for(int j = 0;j < 26;j ++){
			if(fr[j] != -1)
				arr.push_back(fr[j]);
		}
		sort(all(arr));
		for(int j = 0;j < sz(arr);j ++){
			int nxt = n - 1;
			if(j != sz(arr) - 1)
				nxt = arr[j + 1] - 1;
			ld len = (nxt - i + 1);
			ld avg = (j + 1) / len;
			if(avg < an){
				an = avg;
				ans = mk(i + 1, nxt + 1);
			}
		}
	}
	cout << ans.f << " " << ans.s << '\n';
	return 0;
}

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