Submission #671194

#	Time	Username	Problem	Language	Result	Execution time	Memory
671194		Nimbostratus	Nivelle (COCI20_nivelle)	C++17	110 / 110	255 ms	624 KiB

nivelle

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using lint = long long;
const int maxn = 2e5 + 5;
const int inf = 1e9 + 5;
const int mod = 1e9 + 7;

int n;
string s;
int now;
int freq[30];
vector<pair<int, int>> vals;

void add(int x) {
	freq[x]++;
	now += freq[x] == 1;
}

void remove(int x) {
	freq[x]--;
	now -= freq[x] == 0;
}

int check(int k, int d) {
	fill(freq, freq + 26, 0);
	now = 0;
	for(int i = 0; i < k; i++)
		add(s[i] - 'a');
	if(now == d)
		return 0;
	int nowmin = now;
	for(int i = k; i < n; i++) {
		add(s[i] - 'a');
		remove(s[i - k] - 'a');
		nowmin = min(nowmin, now);
		if(now == d)
			return 0;
	}
	return nowmin > d ? 1 : -1;
}

int binsearch(int d) {
	int lo = 1, hi = n, mid;
	while(lo < hi - 1) {
		mid = (lo + hi) / 2;
		int res = check(mid, d);
		if(res == -1)
			lo = mid + 1;
		else if(res == 0)
			lo = mid;
		else
			hi = mid - 1;
	}
	int r1 = check(hi, d);
	int r2 = check(lo, d);
	if(r1 == 0)
		return hi;
	if(r2 == 0)
		return lo;
	return -1;
}

pair<int, int> getrange(int k, int d) {
	fill(freq, freq + 26, 0);
	now = 0;
	for(int i = 0; i < k; i++)
		add(s[i] - 'a');
	if(now == d)
		return {1, k};
	for(int i = k; i < n; i++) {
		add(s[i] - 'a');
		remove(s[i - k] - 'a');
		if(now == d)
			return {i - k + 2, i + 1};
	}
	assert(false);
	return {-1, -1};
}

bool cmp(pair<int, int>& x, pair<int, int>& y) {
	return x.first * y.second < y.first * x.second;
}

signed main() {
	#ifdef Local
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	cin >> s;
	for(int i = 1; i <= 26; i++) {
		int len = binsearch(i);
		if(len != -1)
			vals.push_back({i, len});
	}
	auto res = *min_element(vals.begin(), vals.end(), cmp);
	auto ans = getrange(res.second, res.first);
	cout << ans.first << " " << ans.second << endl;
}

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