oj.uz

답안 #198141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198141 2020-01-24T20:33:15 Z mcdx9524 Nivelle (COCI20_nivelle) C++14
110 / 110
 191 ms 2728 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N = 1e5 + 7;
const int K = 26;
 
struct triple {
    int l, r, c;
};
 
struct ev {
    int l, r;
};
 
struct frac {
    int a, b;
};
 
bool compare(frac x, frac y) {
    int g = __gcd(x.a, x.b);
    x.a /= g;
    x.b /= g;
    g = __gcd(y.a, y.b);
    y.a /= g;
    y.b /= g;
    return x.a * 1ll * y.b < x.b * 1ll * y.a;
}
 
vector <ev> pos[K];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector <triple> e;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && s[i] == s[j]) {
            j++;
        }
        e.push_back({i, j - 1, s[i] - 'a'});
        i = j - 1;
    }
    int sz = (int) e.size();
    for (int i = 0; i < sz; i++) {
        pos[e[i].c].push_back({e[i].l, e[i].r});
    }
    for (int i = 0; i < K; i++) {
        reverse(pos[i].begin(), pos[i].end());
    }
    vector <int> cnt_x(K, 0);
    vector <int> side(K + 7, -1);
    vector <int> l_side(K + 7, -1);
    int diff = 1;
    for (int i = 0; i < sz; i++) {
        cnt_x[e[i].c]++;
        if (cnt_x[e[i].c] == 1) {
            l_side[diff] = e[i].l;
            side[diff] = e[i].r;
            diff++;
        }
    }
    l_side[diff] = n;
    frac ans = {2, 1};
    int ans_l = -1, ans_r = -1;
    for (int i = 1; i <= K; i++) {
        if (side[i] != -1) {
            int cur_x = i;
            int cur_y = l_side[i + 1];
            frac cur = {cur_x, cur_y};
            if (compare(cur, ans)) {
                ans = cur;
                ans_l = 0;
                ans_r = l_side[i + 1] - 1;
            }
        }
    }
    pos[e[0].c].pop_back();
    for (int i = 1; i < sz; i++) {
        int color = e[i - 1].c;
        if (pos[color].empty()) {
            for (int j = 1; j <= K; j++) {
                l_side[j] = l_side[j + 1];
                side[j] = side[j + 1];
            }
        } else {
            int new_l = pos[color].back().l;
            int new_r = pos[color].back().r;
            bool changed = false;
            for (int j = 1; j <= K; j++) {
                if (l_side[j] == -1) {
                    break;
                }
                if (changed) {
                    continue;
                }
                if (l_side[j + 1] < new_l) {
                    l_side[j] = l_side[j + 1];
                    side[j] = side[j + 1];
                } else {
                    changed = true;
                    l_side[j] = new_l;
                    side[j] = new_r;
                }
            }
        }
        for (int j = 1; j <= K; j++) {
            if (side[j] != -1) {
                int cur_x = j;
                int cur_y = l_side[j + 1] - e[i].l;
                frac cur = {cur_x, cur_y};
                if (compare(cur, ans)) {
                    ans = cur;
                    ans_l = e[i].l;
                    ans_r = l_side[j + 1] - 1;
                }
            }
        }
        if (!pos[e[i].c].empty()) {
            pos[e[i].c].pop_back();
        }
    }
    cout << ans_l + 1 << ' ' << ans_r + 1 << '\n';
    return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 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 2 ms 376 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 1 ms 404 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 380 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1076 KB Output is correct
2 Correct 7 ms 1200 KB Output is correct
3 Correct 7 ms 1076 KB Output is correct
4 Correct 7 ms 1076 KB Output is correct
5 Correct 7 ms 1076 KB Output is correct
6 Correct 11 ms 1836 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 2224 KB Output is correct
2 Correct 25 ms 2344 KB Output is correct
3 Correct 42 ms 2224 KB Output is correct
4 Correct 23 ms 1968 KB Output is correct
5 Correct 25 ms 2224 KB Output is correct
6 Correct 28 ms 2224 KB Output is correct

Subtask #5
48.0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 2728 KB Output is correct
2 Correct 171 ms 2600 KB Output is correct
3 Correct 174 ms 2700 KB Output is correct
4 Correct 183 ms 2600 KB Output is correct
5 Correct 165 ms 2600 KB Output is correct
6 Correct 173 ms 2472 KB Output is correct