# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
234829 |
2020-05-25T20:08:30 Z |
doowey |
Nivelle (COCI20_nivelle) |
C++14 |
|
40 ms |
632 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int AL = 26;
int las[AL];
struct F{
int A;
int B;
int li;
int ri;
bool operator< ( const F &C) const {
return A * C.B < C.A * B;
}
};
int main(){
fastIO;
int n;
cin >> n;
for(int i = 0 ; i < AL; i ++ ){
las[i]=-1;
}
F cur = {1, 1, 1, 1};
char in;
int d;
set<int> pos;
pos.insert(0);
int cnt;
for(int i = 1; i <= n; i ++){
cin >> in;
d = in - 'a';
if(las[d] != -1){
pos.erase(las[d]);
}
pos.insert(i);
auto it = pos.end();
it--;
cnt = 0;
F tri;
while(it != pos.begin()){
auto pv = it;
pv -- ;
cnt ++ ;
tri = {cnt, i - (*pv), (*pv) + 1, i};
cur = min(cur, tri);
it = pv;
}
las[d]=i;
}
cout << cur.li << " " << cur.ri << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
512 KB |
Output is correct |
2 |
Correct |
14 ms |
384 KB |
Output is correct |
3 |
Correct |
15 ms |
512 KB |
Output is correct |
4 |
Correct |
14 ms |
384 KB |
Output is correct |
5 |
Correct |
14 ms |
512 KB |
Output is correct |
6 |
Correct |
14 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
384 KB |
Output is correct |
2 |
Correct |
17 ms |
384 KB |
Output is correct |
3 |
Correct |
17 ms |
384 KB |
Output is correct |
4 |
Correct |
18 ms |
384 KB |
Output is correct |
5 |
Correct |
17 ms |
384 KB |
Output is correct |
6 |
Correct |
17 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
384 KB |
Output is correct |
2 |
Correct |
39 ms |
512 KB |
Output is correct |
3 |
Correct |
39 ms |
384 KB |
Output is correct |
4 |
Correct |
38 ms |
632 KB |
Output is correct |
5 |
Correct |
40 ms |
384 KB |
Output is correct |
6 |
Correct |
40 ms |
512 KB |
Output is correct |