Submission #1280792

#TimeUsernameProblemLanguageResultExecution timeMemory
1280792vache_kocharyanNivelle (COCI20_nivelle)C++20
110 / 110
51 ms11012 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int nxt[N][26];
int a[N];

#define UNIQUE_SORT(vec) do { \
	sort((vec).begin(), (vec).end()); \
	(vec).erase(unique((vec).begin(), (vec).end()), (vec).end()); \
} while(0)

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		char c;
		cin >> c;

		a[i] = (c - 'a');
	}

	for (int j = 0; j < 26; j++)
		nxt[n + 1][j] = n + 1;

	for (int i = n; i >= 1; i--)
	{
		for (int j = 0; j < 26; j++)
		{
			nxt[i][j] = nxt[i + 1][j];
		}
		nxt[i][a[i]] = i;
	}
	int ans_l = 1, ans_r = n;
	long double ans = (n);

	for (int i = 1; i <= n; i++)
	{
		vector<int>vec;
		for (int j = 0; j < 26; j++)vec.push_back(nxt[i][j]);

		vec.push_back(n + 1);
		UNIQUE_SORT(vec);
		long double cnt = 1.0000000;
		for (auto j : vec)
		{
			if (i == j)continue;
			int r = j - 1;
			long double ans_x = (cnt / (r - i + 1));
			if (ans > ans_x)
			{
				ans = ans_x;
				ans_l = i;
				ans_r = r;
 			}
			cnt++;
		}
	}
	cout << ans_l << " " << ans_r << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...