Submission #75823279

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("O3,fast-math")
using namespace std;
using ll = long long;
int n,q,op,a,b,c;
vector<vector<int>> qry;
bool tryy(int s) {
    //cout << "try " << s << endl;
    int ignore=n-s, curserv=s;
    bitset<2020> dp; // master on
    if(curserv==0) dp[0]=1;
    for(int i=1;i<=curserv;i++) dp[i]=1;
    for(auto qq:qry) {
        int op=qq[0], a=qq[1], b=qq[2], c=qq[3];
        //cout << "dp "; for(int i=0;i<=n;i++) cout << dp[i] << " "; cout << endl;
        if(op==1) {
            if(!curserv) continue;
            if(ignore) ignore--;
            else {
                dp[curserv]=0;
                curserv--;
                dp=dp|dp>>1; 
                if(curserv) dp[0]=0;
            }
        }
        if(op==2) {
            if(!curserv && a+b+c==0) continue;
            if(curserv < a+b+c) return false;
            for(int i=0;i<a;i++) dp[i]=0;
            for(int i=-2;i<c;i++) dp[curserv-i]=0;
        }
    }
    //cout << "dp "; for(int i=0;i<=n;i++) cout << dp[i] << " "; cout << endl;
    for(int i=0;i<=curserv;i++) if(dp[i]) return true;
    return false;
}
int alive[2020];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;i++) alive[i]=1;
    for(int i=1;i<=q;i++) {
        cin >> op >> a;
        if(op==1 && alive[a]) alive[a]=0, qry.push_back({1,a,-1,-1});
        if(op==2) cin >> b >> c, qry.push_back({2,a,b,c});
    }

    // parametric
    /*
    int no=-1, yes=n+1;
    while(no+1<yes) {
        int mid = (no+yes)>>1;
        //cout << "try" << mid << endl;
        if(tryy(mid)) yes=mid;
        else no=mid;
    }
    */
    for(int i=0;i<=n;i++) {
        if(tryy(i)) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    //cout << (yes==n+1 ? -1 : yes);
}

Submission Info

Judge Result