oj.uz

Submission #198007

# Submission time Handle Problem Language Result Execution time Memory
198007 2020-01-24T13:05:07 Z ami Nivelle (COCI20_nivelle) C++17
110 / 110
 324 ms 632 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 276 KB Output is correct
6 Correct 3 ms 376 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 9 ms 376 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 504 KB Output is correct
2 Correct 30 ms 600 KB Output is correct
3 Correct 30 ms 624 KB Output is correct
4 Correct 28 ms 504 KB Output is correct
5 Correct 30 ms 632 KB Output is correct
6 Correct 42 ms 632 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 632 KB Output is correct
2 Correct 64 ms 632 KB Output is correct
3 Correct 64 ms 504 KB Output is correct
4 Correct 63 ms 588 KB Output is correct
5 Correct 64 ms 596 KB Output is correct
6 Correct 75 ms 632 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 632 KB Output is correct
2 Correct 277 ms 632 KB Output is correct
3 Correct 266 ms 604 KB Output is correct
4 Correct 278 ms 632 KB Output is correct
5 Correct 291 ms 604 KB Output is correct
6 Correct 324 ms 504 KB Output is correct