제출 #198007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198007		ami	Nivelle (COCI20_nivelle)	C++17	110 / 110	324 ms	632 KiB

nivelle

#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
#define num first
#define den second
using namespace std;
using ll = long long;
using frac = pair<int,int>;

int N;
string S;
pair<frac,pair<int,int>> res;

void check_res(int a,int b,int l,int r) {
	if (res.first.num*b>res.first.den*a) {
		res={frac(a,b),make_pair(l,r)};
	}
}

void solve(int c) {
	map<int,int> cnt;
	auto dec=[&](int i) {
		cnt[i]--;
		if (cnt[i]==0) cnt.erase(i);
	};
	int l=0;
	rep(r,0,N) {
		cnt[S[r]-'a']++;
		while (l<r && sz(cnt)>c) dec(S[l++]-'a');
		check_res(sz(cnt),r-l+1,l,r);
	}
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>N>>S;

	set<char> ss(S.begin(),S.end());
	res={frac(sz(ss),N),make_pair(0,N-1)};

	rep(i,1,27) solve(i);
	cout<<res.second.first+1<<" "<<res.second.second+1<<'\n';
}

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