Submission #1280792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280792		vache_kocharyan	Nivelle (COCI20_nivelle)	C++20	110 / 110	51 ms	11012 KiB

nivelle

#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;
}

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