Submission #846615

#	Time	Username	Problem	Language	Result	Execution time	Memory
846615		vjudge1	Nivelle (COCI20_nivelle)	C++11	110 / 110	424 ms	856 KiB

nivelle

#include <bits/stdc++.h>
#define lg(a) (31 - __builtin_clz((a)))
#define endl ("\n")
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
const ll MOD = 1e9+7;
using namespace std;
/*

*/




void solve(){
	int N; cin >> N;
	string s; cin >> s;

	set<char> col;
	for(auto c:s){
		col.insert(c);
	}
	int C = col.size();
	col.clear();

	map<char, int> cnt;
	double average = 2;
	int l=0, r=N-1;
	for(int k=1;k<=C;k++){
		int R = -1;
		col.clear(); cnt.clear();
		for(int L = 0;L<N;L++){

			while(R!=N-1){
				R++;
				col.insert(s[R]);
				if(col.size()==k+1){
					col.erase(s[R]);
					R--;
					break;
				}
				else{
					cnt[s[R]]++;
				}
			}
			if((double) (k)/(R-L+1) < average){
				average = (double) (k)/(R-L+1);
				l = L, r = R;
				// cout<<L+1<<' '<<R+1<< ' '<<average<<endl;
			}

			cnt[s[L]]--;
			if(cnt[s[L]]==0) col.erase(s[L]);
		}
	}
	cout<<l+1<<' '<<r+1<<endl;

}

int main(){
	int test; 
    // cin >> test;
    test =1;
   	while (test--){
		solve();
    }
}

Compilation message (stderr)

nivelle.cpp: In function 'void solve()':
nivelle.cpp:41:18: warning: comparison of integer expressions of different signedness: 'std::set<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     if(col.size()==k+1){
      |        ~~~~~~~~~~^~~~~

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