#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, P=5000, Q=1, l=1, r=1;
string s;
cin >> n >> s;
map<char, vector<int> > mp;
for(int i=0; i<n; i++) mp[s[i]].push_back(i);
for(char ch='a'; ch<='z'; ch++) mp[ch].push_back(n);
for(int i=0; i<n; i++) {
vector<int> v;
for(char ch='a'; ch<='z'; ch++) {
int p = lower_bound(mp[ch].begin(), mp[ch].end(), i) - mp[ch].begin();
if(mp[ch][p] != n) v.push_back(mp[ch][p]);
}
sort(v.begin(), v.end());
if(v.back() != n) v.push_back(n);
for(int j=0; j<v.size()-1; j++) {
int A = j + 1, B = v[j+1] - i;
if(P * B > Q * A) {
P = A, Q = B;
l = i, r = v[j+1]-1;
}
}
}
cout << l+1 << " " << r+1 << '\n';
return 0;
}
Compilation message
nivelle.cpp: In function 'int main()':
nivelle.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int j=0; j<v.size()-1; j++) {
| ~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
348 KB |
Output is correct |
2 |
Correct |
4 ms |
348 KB |
Output is correct |
3 |
Correct |
4 ms |
348 KB |
Output is correct |
4 |
Correct |
4 ms |
460 KB |
Output is correct |
5 |
Correct |
4 ms |
348 KB |
Output is correct |
6 |
Correct |
4 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
1240 KB |
Output is correct |
2 |
Correct |
87 ms |
1240 KB |
Output is correct |
3 |
Correct |
87 ms |
1240 KB |
Output is correct |
4 |
Correct |
89 ms |
1240 KB |
Output is correct |
5 |
Correct |
86 ms |
1240 KB |
Output is correct |
6 |
Correct |
88 ms |
1156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
111 ms |
860 KB |
Output is correct |
2 |
Correct |
103 ms |
1116 KB |
Output is correct |
3 |
Correct |
104 ms |
1116 KB |
Output is correct |
4 |
Correct |
105 ms |
1168 KB |
Output is correct |
5 |
Correct |
119 ms |
860 KB |
Output is correct |
6 |
Correct |
103 ms |
1112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
193 ms |
1172 KB |
Output is correct |
2 |
Correct |
188 ms |
1368 KB |
Output is correct |
3 |
Correct |
186 ms |
1124 KB |
Output is correct |
4 |
Correct |
189 ms |
1116 KB |
Output is correct |
5 |
Correct |
191 ms |
1064 KB |
Output is correct |
6 |
Correct |
195 ms |
860 KB |
Output is correct |