oj.uz

Submission #493942

# Submission time Handle Problem Language Result Execution time Memory
493942 2021-12-13T12:34:50 Z balbit DEL13 (info1cup18_del13) C++14
40 / 100
 7 ms 972 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is partially correct
2 Correct 1 ms 204 KB Output is partially correct

Subtask #2
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is partially correct
2 Correct 1 ms 204 KB Output is partially correct
3 Correct 4 ms 460 KB Output is partially correct
4 Correct 5 ms 332 KB Output is partially correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is partially correct
2 Correct 2 ms 372 KB Output is partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is partially correct
2 Correct 1 ms 204 KB Output is partially correct
3 Correct 4 ms 460 KB Output is partially correct
4 Correct 5 ms 332 KB Output is partially correct
5 Correct 1 ms 332 KB Output is partially correct
6 Correct 1 ms 332 KB Output is partially correct
7 Correct 1 ms 332 KB Output is partially correct

Subtask #5
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is partially correct
2 Correct 1 ms 204 KB Output is partially correct
3 Correct 4 ms 460 KB Output is partially correct
4 Correct 5 ms 332 KB Output is partially correct
5 Correct 1 ms 332 KB Output is partially correct
6 Correct 1 ms 332 KB Output is partially correct
7 Correct 1 ms 332 KB Output is partially correct
8 Correct 7 ms 588 KB Output is partially correct
9 Correct 5 ms 848 KB Output is partially correct
10 Correct 5 ms 844 KB Output is partially correct
11 Correct 6 ms 972 KB Output is partially correct