Submission #1269168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269168		phancddev	MP3 Player (CEOI10_mp3player)	C++20	40 / 100	1095 ms	1604 KiB

mp3player

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Vmax, V2;
    if (!(cin >> N >> Vmax >> V2)) return 0;

    vector<char> op(N + 1);
    vector<int> t(N + 1);

    for (int i = 1; i <= N; ++i) {
        char c; int ti;
        cin >> c >> ti;
        op[i] = c;
        t[i] = ti;
    }

    vector<int> diffs; diffs.reserve(max(0, N - 1));
    for (int i = 2; i <= N; ++i) diffs.push_back(t[i] - t[i - 1]);

    vector<int> uniq = diffs;
    sort(uniq.begin(), uniq.end());
    uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());

    auto simulate = [&](int threshold, int start) -> int {
        int v = start;
        for (int i = 2; i <= N; ++i) {
            int delta = t[i] - t[i - 1];
            if (delta <= threshold) {
                if (op[i] == '+') {
                    if (v < Vmax) ++v;
                } else {
                    if (v > 0) --v;
                }
            }
        }
        return v;
    };

    auto inRange = [&](int threshold) -> pair<int,int> {
        int a = simulate(threshold, 0);
        int b = simulate(threshold, Vmax);
        if (a > b) swap(a, b);
        return {a, b};
    };

    auto maxV1For = [&](int threshold, int target) -> int {
        int lo = 0, hi = Vmax;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            int fmid = simulate(threshold, mid);
            if (fmid <= target) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    };

    if (uniq.empty()) {
        cout << "infinity\n";
        return 0;
    }

    {
        int d_last = uniq.back();
        auto [L, R] = inRange(d_last);
        if (L <= V2 && V2 <= R) {
            cout << "infinity\n";
            return 0;
        }
    }

    for (int j = (int)uniq.size() - 2; j >= 0; --j) {
        int thr = uniq[j];
        auto [L, R] = inRange(thr);
        if (L <= V2 && V2 <= R) {
            int T_ans = uniq[j + 1] - 1;
            int V1_ans = maxV1For(thr, V2);
            cout << T_ans << ' ' << V1_ans << "\n";
            return 0;
        }
    }

    {
        int T_ans = uniq.front() - 1;
        int V1_ans = V2;
        cout << T_ans << ' ' << V1_ans << "\n";
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10