Submission #1271768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271768		cbnk32_tuandung	Nivelle (COCI20_nivelle)	C++17	110 / 110	21 ms	584 KiB

nivelle

/*  _  _   ___   __  ___  ___  _  _  ___  __   ___     _   _  ___   ___  __   _____  _  _  ___       */
/* | || | /_\ \ / / / __|/ _ \| \| |/ __| \ \ / /_\   | | | |/ _ \ / __| \ \ / / _ \| \| |/ __|      */
/* | __ |/ _ \ V /  \__ \ (_) | .` | (_ |  \ V / _ \  | |_| | (_) | (__   \ V / (_) | .` | (_ |      */
/* |_||_/_/_\_\_|___|___/\___/|_|\_|\___|   \_/_/_\_\ _\___/ \___/ \___| _ \_/_\___/|_|\_|\___| ___  */
/* |   \| __| |_   _| || | /_\ \ / / |   \ / _ \_ _| |  \/  | __| \| | || | |  \/  |/ _ \| \| |/ __| */
/* | |) | _|    | | | __ |/ _ \ V /  | |) | (_) | |  | |\/| | _|| .` | __ | | |\/| | (_) | .` | (_ | */
/* |___/|___|   |_| |_||_/_/ \_\_|   |___/ \___/___| |_|  |_|___|_|\_|_||_| |_|  |_|\___/|_|\_|\___| */

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

int n;
int a[100009];
int xh[100009];

int main() {
	ios_base::sync_with_stdio(1+1==3);
	cout.tie(nullptr); cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		char x; cin >> x;
		a[i]=(int) (x-'a');
	}
	double drr=(double)1e9+7;
	int lans=1, rans = n;
	for (int diff = 1; diff <= 26; ++diff) {
		int l=1,r=1;
		xh[a[1]]=true;
		int dem=1;
		while (l<n && r < n) {
			if (dem<=diff) {
				++r;
				if (xh[a[r]]==0) {
					++dem;
				}
				xh[a[r]]++;
			} else {
				xh[a[l]]--;
				if (xh[a[l]]==0) --dem;
				++l;
			}
			double tmp = 1.0*dem/(r-l+1);
			if (tmp<drr) {
				drr=tmp;
				lans=l; rans=r;
			}
		}
		for (int i=0; i <= 25; ++i) xh[i]=0;
	}
	cout << lans << " " << rans;
}

/*
Hôm nay trời vẫn mưa tầm tã,trốn việc lang thang một tiếng trên đường..
Từng hạt mưa rơi xuống đầu,văng xuống đường, tan ra từng mảnh vụn,hòa vào dòng nước...rồi theo nhau chui vào lỗ cống..he he
*/

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