Submission #844476

#TimeUsernameProblemLanguageResultExecution timeMemory
844476vjudge1Nivelle (COCI20_nivelle)C++17
110 / 110
26 ms1368 KiB
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define int long long

const int modulo = 1e9 + 7;

int arr[N];

int32_t main()
{
	fastio();

	int n;
	cin>>n;

	for (int i = 1; i <= n; i++){
		char c;
		cin>>c;
		arr[i] = c - 'a';
	}


	pii ans = {1, 1}, res = {1, 1};

	for (int i = 1; i <= 26; i++){
		int maks = 0;
		vector<int> cnt(26, 0);
		int tot = 1, r = 1;
		cnt[arr[1]] = 1;
		while(r < n){
			if (cnt[arr[r + 1]] > 0 || tot < i){
				cnt[arr[r + 1]]++;
				if (cnt[arr[r + 1]] == 1) tot++;
				r++;
			}
			else break;
		}
		maks = r;
		if (ans.st * maks > i * ans.nd){
			ans = {i, r};
			res = {1, r};
		}
		for (int j = 2; j <= n; j++){
			cnt[arr[j - 1]]--;
			if (cnt[arr[j - 1]] == 0) tot--;
			while(r < n){
				if (cnt[arr[r + 1]] > 0 || tot < i){
					cnt[arr[r + 1]]++;
					if (cnt[arr[r + 1]] == 1) tot++;
					r++;
				}
				else break;
			}
			if (maks < r - j + 1){
				maks = r - j + 1;
				if (ans.st * maks > i * ans.nd){
					ans = {i, r - j + 1};
					res = {j, r};
				}
			}
		}
	}

	cout<<res.st<<sp<<res.nd<<endl;

	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...