Submission #231826

#	Time	Username	Problem	Language	Result	Execution time	Memory
231826		CodeTiger927	Nivelle (COCI20_nivelle)	C++14	110 / 110	120 ms	11384 KiB

nivelle

using namespace std;

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

#define MAXN 100005

int arr[MAXN];
string str;
int N;
int nextAppear[MAXN][26];

int main() {
	cin >> N >> str;
	for(int i = 0;i < N;i++) {
		arr[i] = str.at(i) - 'a';
	}
	for(int i = 0;i < 26;i++) {
		nextAppear[N][i] = N;
	}
	for(int i = N - 1;i >= 0;--i) {
		for(int j = 0;j < 26;j++) {
			nextAppear[i][j] = nextAppear[i + 1][j];
		}
		nextAppear[i][arr[i]] = i;
	}
	int ansL;
	int ansR;
	double ans = MAXN;
	for(int i = 0;i < N;i++) {
		vector<int> v;
		int active = 0;
		for(int j = 0;j < 26;j++) {
			if(nextAppear[i][j] != N) v.push_back(nextAppear[i][j]);
			if(nextAppear[i][j] != N) active++;
		}
		sort(v.begin(),v.end());
		double cur = 1.0 * active / (N - i);
		if(cur < ans) {
			ansL = i;
			ansR = N - 1;
			ans = cur;
		}
		for(int j = 1;j < v.size();j++) {
			double next = 1.0 * j / (v[j] - i);
			if(next < ans) {
				ansL = i;
				ansR = v[j] - 1;
				ans = next;
			}
		}
	}
	cout << (ansL + 1) << " " << (ansR + 1) << endl;

}

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1;j < v.size();j++) {
                 ~~^~~~~~~~~~
nivelle.cpp:55:40: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << (ansL + 1) << " " << (ansR + 1) << endl;
                                        ^
nivelle.cpp:55:24: warning: 'ansL' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << (ansL + 1) << " " << (ansR + 1) << endl;
                        ^~~

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