Submission #493942

#	Time	Username	Problem	Language	Result	Execution time	Memory
493942		balbit	DEL13 (info1cup18_del13)	C++14	40 / 100	7 ms	972 KiB

del13

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

#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 2e5+5;
bool dp[maxn][3]; // none, even, odd

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    int T; cin>>T;
    while (T--) {
        int N, m; cin>>N>>m;
        vector<int> a;
        a.pb(0);
        REP(i,m) {
            int x; cin>>x; a.pb(x);
        }
        a.pb(N+1);
        sort(ALL(a));
        dp[0][0] = 1;
        for (int i = 1; i<SZ(a); ++i) {
            memset(dp[i], 0, sizeof dp[i]);
            int df = a[i] - a[i-1] - 1;
            if (df == 0) {
                dp[i][0] = dp[i-1][0];
            }else{
                if (df % 2 == 0) {
                    dp[i][0] = dp[i-1][1]; // if even, can del everything
                    dp[i][2] = dp[i-1][2]; // if odd, leaves me with odd
                    dp[i][1] = (df >= 4 && dp[i-1][1]) || dp[i-1][0]; // if even and leaves me space, ok
                }else{
                    dp[i][0] = dp[i-1][2];
                    dp[i][2] = (df >= 3 && dp[i-1][1]) || dp[i-1][0]; // i want odd number left
                    dp[i][1] = (df >= 2 && dp[i-1][2]); // i want even left, so i want to remove odd number
                }
            }
            bug(i, df, dp[i][0], dp[i][1], dp[i][2]);
        }
        if (dp[SZ(a)-1][0]) {
            cout<<0<<endl<<endl;
        }else{
            cout<<-1<<endl;
        }

    }

}

• Subtask 1: 6 / 15
• Subtask 2: 6 / 15
• Subtask 3: 6 / 15
• Subtask 4: 10 / 25
• Subtask 5: 12 / 30