Submission #1323172

#TimeUsernameProblemLanguageResultExecution timeMemory
1323172syanvuMP3 Player (CEOI10_mp3player)C++20
30 / 100
1096 ms4040 KiB
// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e4 + 1, MX = 40, inf = 1e18;

void solve(){
    int n, vmx, vf;
    cin >> n >> vmx >> vf;
    pair<char, int> p[n + 1];
    p[0].second = 0;
    int cm = 0, cp = 0, mx = 0;
    vector<int> v;
    for(int i = 1; i <= n; i++){
        cin >> p[i].first >> p[i].second;
        v.push_back(p[i].second - p[i - 1].second);
        v.push_back(p[i].second - p[i - 1].second - 1);
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    int rest = 0, resv = 0;
    for(int vs = 0; vs <= vmx; vs++){
        int cur = vs;
        for(int i = 2; i <= n; i++){
            cur = max(0ll, cur - (p[i].first == '-'));
            cur = min(vmx, cur + (p[i].first == '+'));
        }
        if(cur == vf){
            cout << "infinty";
            return;
        }
    }
    for(int j = v.size() - 1; j >= 0 && v[j] >= 0; j--){
        int t = v[j];
        int vs = -1;
        int l = 0, r = vmx;
        while(l <= r){
            int mid = (l + r) / 2;
            int cur = mid;
            for(int i = 2; i <= n; i++){
                if(p[i].second - p[i - 1].second <= t){
                    cur = max(0ll, cur - (p[i].first == '-'));
                    cur = min(vmx, cur + (p[i].first == '+'));
                }
            }
            if(cur == vf){
                vs = max(vs, mid);
                l = mid + 1;
            }
            else if(cur < vf){
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if(vs != -1){
            cout << t << ' ' << vs << '\n';
            return;
        }
    }
    cout << 0 << ' ' << vf << '\n';
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t; 
    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...