oj.uz

Submission #197961

# Submission time Handle Problem Language Result Execution time Memory
197961 2020-01-24T12:14:59 Z model_code Nivelle (COCI20_nivelle) C++17
110 / 110
 11 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

const int ALPHA = 26;
  
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    string s;
    cin >> n >> s;

    int sol_cnt = ALPHA, sol_l = -1, sol_r = -1;

    vector<int> last(ALPHA, -1), sorted(ALPHA + 1, -1);
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        sorted.erase(find(sorted.begin(), sorted.end(), last[c]));
        last[c] = i;
        sorted.insert(sorted.begin(), i);

        for (int j = 1; j <= ALPHA; j++)
            if (j * (sol_r - sol_l + 1) < sol_cnt * (i - sorted[j])) {
                sol_cnt = j;
                sol_l = sorted[j] + 1;
                sol_r = i;
            }
    }

    cout << sol_l + 1 << " " << sol_r + 1 << "\n";

    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 508 KB Output is correct
2 Correct 10 ms 540 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 10 ms 632 KB Output is correct
5 Correct 11 ms 476 KB Output is correct
6 Correct 10 ms 504 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 11 ms 508 KB Output is correct
3 Correct 10 ms 632 KB Output is correct
4 Correct 10 ms 504 KB Output is correct
5 Correct 10 ms 504 KB Output is correct
6 Correct 10 ms 504 KB Output is correct