Submission #198141

#	Time	Username	Problem	Language	Result	Execution time	Memory
198141		mcdx9524	Nivelle (COCI20_nivelle)	C++14	110 / 110	191 ms	2728 KiB

nivelle

#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 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 48 / 48