Pinely Round 5 (Div. 1 + Div. 2)

Pinely Round 5 (Div. 1 + Div. 2)

Date

A	B	C	D1	D2	E1	E2	F
O	O	O	Ø	Ø

E - Left is Always Right

D - Locked Out

void solve() {
    int n = read();

    vector<int> a(n);
    for (auto &x : a) x = read();

    vector<vector<int>> pos(n + 2);
    for (int i = 0; i < n; i++) pos[a[i]].eb(i);

    vector<int> cnt(n + 2, 0);
    for (int i = 1; i <= n; i++) cnt[i] = pos[i].size();

    vector<int> m(n + 2, 0);
    for (int v = 2; v <= n; v++) {
        auto &L = pos[v - 1];
        auto &R = pos[v];
        int i = 0, j = 0;
        while (i < L.size() and j < R.size()) {
            if (L[i] < R[j]) {
                m[v]++, i++, j++;
            } else {
                j++;
            }
        }
    }

    int ans = 0, las = 0;
    for (int v = 2; v <= n; v++) {
        int rem = cnt[v - 1] - las;
        if (rem < 0) rem = 0;

        int res = min(m[v], rem);
        ans += res;
        las = res;
    }

    cout << ans << '\n';
}

C - Loyalty

void solve() {
    int n = read();
    int X = read();

    vector<int> a(n);
    for (auto &x : a) x = read();

    ranges::sort(a);

    int rem = 0;
    int ans = 0;
    vector<int> p;
    
    for (int l = 0, r = n - 1; l <= r; ) {
        int need = X - rem;
        if (a[r] >= need) {
            ans += a[r];
            rem = (rem + a[r]) % X;
            p.eb(a[r]);
            --r;
        } else {
            rem = (rem + a[l]) % X;
            p.eb(a[l]);
            ++l;
        }
    }
    
    cout << ans << "\n";
    for (int i = 0; i < n; i++) {
        cout << p[i] << " \n"[i == n - 1];
    }
}

B - Make Connected

void solve() {
    int n = read();
    vector<string> g(n);
    for (auto &s : g) cin >> s;

    set<int> s[4] {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == '.') continue;
            s[0].ep(i + j);
            s[1].ep(i - j);
            s[2].ep(i);
            s[3].ep(j);
        }
    }

    auto check = [&](auto s) {
        return s.size() < 2 or *s.begin() + 1 == *s.rbegin();
    };

    int ans = check(s[0]) or check(s[1]) or (check(s[2]) and check(s[3]));
    cout << (ans ? "YES\n" : "NO\n");
}

A - Round Trip

void solve() {
    int R0 = read();
    int X = read();
    int D = read();
    int n = read();

    string s; cin >> s;

    int ans = 0;
    int R = R0;
    for (auto ch : s) {        
        if (ch == '1') {
            ans++;
            if (R >= X) {
                R = max(0ll, R - D);
            }
        } else {
            if (R < X) {
                ans++;
            }
        }
    }

    cout << ans << '\n';
}