Submission #1092754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092754		Hacv16	Nivelle (COCI20_nivelle)	C++17	110 / 110	42 ms	668 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2e5 + 5;

int n;
char t[MAX];

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

	cin >> n;

	for(int i = 1; i <= n; i++)
		cin >> t[i];

	int L, R;
	double minColorfulness = 1e8;

	vector<int> lastAp(26, -1);
	set<int> s; s.insert(0);

	for(int i = 1; i <= n; i++)
	{
		if(lastAp[ t[i] - 'a' ] != -1)
			s.erase( lastAp[ t[i] - 'a' ] );

		lastAp[ t[i] - 'a' ] = i;
		s.insert(i);

		vector<int> aux = vector<int>(s.begin(), s.end());

		for(int j = aux.size() - 1, numDistinct = 1; j >= 1; j--, numDistinct++)
		{
			int leftBound = aux[ j - 1 ] + 1;
			int range = (i - leftBound + 1);

			double curColorfulness = (double)(numDistinct)/(double)(range);

			if(curColorfulness < minColorfulness)
			{
				L = leftBound; R = i;
				minColorfulness = curColorfulness;
			}
		}
	}

	// cerr << minColorfulness << '\n';

	cout << L << ' ' << R << '\n';
}

Compilation message (stderr)

nivelle.cpp: In function 'int32_t main()':
nivelle.cpp:52:27: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |  cout << L << ' ' << R << '\n';
      |                           ^~~~
nivelle.cpp:52:15: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |  cout << L << ' ' << R << '\n';
      |               ^~~

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