#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main(){
int n;cin>>n;
string str;cin>>str;
vector<int> ilk(26,-1);
vector<int> kuc(26,0);
int frac1=1,frac2=1;
int ansl=0,ansr=0;
for (int i = n-1; i >= 0; i--){
ilk[str[i]-'a']=i;
int crr = 0;
for (int j = 0; j < 26; ++j)
{
if (ilk[j]!=-1) crr++;
}
if (crr*frac2<(n-i+1)*frac1){
frac1=crr;
frac2=n-i;
ansl=i;
ansr=n-1;
}
for (int j = 0; j < 26; j++){
if (ilk[j]==-1) continue;
if (ilk[j]==i) continue;
int crrr = 0;
for (int k = 0; k < 26; k++){
if (ilk[k]!=-1 && ilk[k]<=ilk[j]-1){
crrr++;
}
}
if (crrr==0) continue;
if (crrr*frac2<(ilk[j]-i)*frac1){
frac1=crrr;
frac2=ilk[j]-i;
ansl=i;
ansr=ilk[j]-1;
}
}
}
cout<<ansl+1<<" "<<ansr+1<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
348 KB |
Output is correct |
2 |
Correct |
3 ms |
344 KB |
Output is correct |
3 |
Correct |
3 ms |
344 KB |
Output is correct |
4 |
Correct |
3 ms |
344 KB |
Output is correct |
5 |
Correct |
3 ms |
348 KB |
Output is correct |
6 |
Correct |
3 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
600 KB |
Output is correct |
2 |
Correct |
8 ms |
600 KB |
Output is correct |
3 |
Correct |
7 ms |
604 KB |
Output is correct |
4 |
Correct |
7 ms |
600 KB |
Output is correct |
5 |
Correct |
7 ms |
600 KB |
Output is correct |
6 |
Correct |
7 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
904 KB |
Output is correct |
2 |
Correct |
15 ms |
600 KB |
Output is correct |
3 |
Correct |
15 ms |
652 KB |
Output is correct |
4 |
Correct |
15 ms |
600 KB |
Output is correct |
5 |
Correct |
15 ms |
600 KB |
Output is correct |
6 |
Correct |
16 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
600 KB |
Output is correct |
2 |
Correct |
135 ms |
600 KB |
Output is correct |
3 |
Correct |
131 ms |
628 KB |
Output is correct |
4 |
Correct |
138 ms |
624 KB |
Output is correct |
5 |
Correct |
142 ms |
600 KB |
Output is correct |
6 |
Correct |
156 ms |
848 KB |
Output is correct |