제출 #1017284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017284		vjudge1	Nivelle (COCI20_nivelle)	C++17	110 / 110	886 ms	21332 KiB

nivelle

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 1e5 + 1;

int pre[M][26];

int dis(int l,int r)
{
	int ans=0;
	for (int i=0;i<26;i++)
		if (pre[r][i]-pre[l][i])
			ans++;
	return ans;
}

bool grt(pair<int,int> p,pair<int,int> p1)
{
	int l=p.second-p.first,l1=p1.second-p1.first;
	int a=dis(p.first,p.second),b=dis(p1.first,p1.second);
	int x=lcm(l,l1);
	a*=x/l,b*=x/l1;
	return a>b;
}

signed main()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<26;j++)
			pre[i+1][j]=pre[i][j];
		pre[i+1][s[i]-'a']++;
	}
	vector<pair<int,int>> vec;
	for (int dif=1;dif<26;dif++)
	{
		int l=0,r=0;
		for (int i=0;i<n;i++)
		{
			int s=i+1,e=n+1;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (dis(i,mid)<=dif)
					s=mid;
				else
					e=mid;
			}
			if (s-i>r-l)
				l=i,r=s;
		}
		vec.push_back({l,r});
	}
	vec.push_back({0,n});
	int sz=26;
	while (vec.size()>1)
	{
		if (grt(vec[sz-2],vec.back()))
			swap(vec[sz-2],vec.back());
		vec.pop_back();
		sz--;
	}
	cout<<vec[0].first+1<<' '<<vec[0].second<<endl;
	
	return 0;
}

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