oj.uz

Submission #671194

# Submission time Handle Problem Language Result Execution time Memory
671194 2022-12-12T10:44:35 Z Nimbostratus Nivelle (COCI20_nivelle) C++17
110 / 110
 255 ms 624 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 320 KB Output is correct
2 Correct 3 ms 320 KB Output is correct
3 Correct 4 ms 324 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 4 ms 320 KB Output is correct
6 Correct 4 ms 320 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 612 KB Output is correct
2 Correct 168 ms 608 KB Output is correct
3 Correct 168 ms 612 KB Output is correct
4 Correct 165 ms 596 KB Output is correct
5 Correct 173 ms 608 KB Output is correct
6 Correct 178 ms 612 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 608 KB Output is correct
2 Correct 179 ms 612 KB Output is correct
3 Correct 184 ms 596 KB Output is correct
4 Correct 176 ms 608 KB Output is correct
5 Correct 169 ms 624 KB Output is correct
6 Correct 185 ms 612 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 620 KB Output is correct
2 Correct 186 ms 616 KB Output is correct
3 Correct 244 ms 612 KB Output is correct
4 Correct 180 ms 612 KB Output is correct
5 Correct 209 ms 612 KB Output is correct
6 Correct 255 ms 596 KB Output is correct