Submission #256183

#	Time	Username	Problem	Language	Result	Execution time	Memory
256183		blacktulip	Nivelle (COCI20_nivelle)	C++17	110 / 110	50 ms	760 KiB

nivelle

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,l,r;
double cev=inf;
map<char,int> mpp;
string s;
vector<int> v;

main(void){
	cin>>n>>s;
	for(int i=1;i<=26;i++)a[i]=-inf;
	for(int i='a';i<='z';i++)mpp[i]=-1;
	for(int i=0;i<n;i++){
		if(mpp[s[i]]==-1){
			mpp[s[i]]=i;
			for(int j=1;j<=26;j++){
				//~ if(a[i][])
				//~ printf("%lf\n",j/(double)(i-a[j]));
				if(a[j]!=-inf)if((j)/(double)(i-a[j])<cev){l=a[j]+1;r=i;}
				if(a[j]!=-inf)cev=min(cev,(j)/(double)(i-a[j]));
				//~ if(j!=1)a[j]=a[j-1];
			}
			for(int j=26;j>=1;j--){
				if(j!=1)a[j]=a[j-1];
			}
			//~ cout<<"**\n";
			a[1]=i;
		}
		else{
			for(int j=1;j<=26;j++){
				if(a[j]!=-inf)if((j)/(double)(i-a[j])<cev){l=a[j]+1;r=i;}
				if(a[j]!=-inf)cev=min(cev,(j)/(double)(i-a[j]));
			}
			for(int j=26;j>=1;j--){
				
				if(j!=1 && a[j]>mpp[s[i]])a[j]=a[j-1];
			}
			if(a[1]>mpp[s[i]])a[1]=i;
			mpp[s[i]]=i;
		}
		//~ cout<<a[2]<<endl;
		//~ else a[1]=i;
	}
	for(int j=1;j<=26;j++){
		//~ cout<<(j)/(double)(n-a[j])<<"()()"<<endl;
		if(a[j]!=-inf)if((j)/(double)(n-a[j])<cev){l=a[j]+1;r=n;}
		if(a[j]!=-inf)cev=min(cev,(j)/(double)(n-a[j]));
		//~ cout<<cev<<"(()()()"<<endl;
	}
	printf("%lld %lld\n",l,r);
	return 0;
}

Compilation message (stderr)

nivelle.cpp:31:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^

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