oj.uz

Submission #400546

# Submission time Handle Problem Language Result Execution time Memory
400546 2021-05-08T10:05:05 Z dolphingarlic DEL13 (info1cup18_del13) C++14
40 / 100
 29 ms 844 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int p[100002];
bool dp[100002][3];
vector<int> moves;

// void solve(array<int, 3> seg) {
//     if (seg[2] == seg[0]) return;
//     if ((seg[2] - seg[0]) & 1) {
//         impossible = true;
//         return;
//     }
//     moves.push_back(seg[1]);
//     if (seg[2] - seg[1] == seg[1] - seg[0])
//         solve({seg[0] + 1, seg[1], seg[2] - 1});
//     else if (seg[2] - seg[1] == 1)
//         solve({seg[0], (seg[0] + seg[2] - 2) / 2, seg[2] - 2});
//     else if (seg[1] - seg[0] == 1)
//         solve({seg[0] + 2, (seg[0] + seg[2] + 2) / 2, seg[2]});
//     else
//         solve({seg[0] + 1, seg[1], seg[2] - 1});
// }

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        moves.clear();
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; i++) cin >> p[i];
        p[0] = 0, p[m + 1] = n + 1;

        memset(dp, 0, sizeof dp);
        dp[0][0] = true;
        for (int i = 1; i <= m + 1; i++) {
            if (p[i] - p[i - 1] == 1) dp[i][0] |= dp[i - 1][0];
            else dp[i][0] |= dp[i - 1][1 + (p[i] - p[i - 1]) % 2];

            if ((p[i] - p[i - 1]) % 2 == 0) {
                dp[i][1] |= dp[i - 1][0];
                if (p[i] - p[i - 1] > 2) {
                    dp[i][1] |= dp[i - 1][2];
                    dp[i][2] |= dp[i - 1][1];
                }
            } else if (p[i] - p[i - 1] > 1) {
                dp[i][2] |= dp[i - 1][0];
                dp[i][1] |= dp[i - 1][1];
                if (p[i] - p[i - 1] > 3)
                    dp[i][2] |= dp[i - 1][2];                    
            }
        }

        // for (int j = 0; j < 3; j++) {
        //     for (int i = 0; i <= m + 1; i++) {
        //         cout << dp[i][j] << ' ';
        //     }
        //     cout << '\n';
        // }
        // for (int j = 1; j <= m; j++) cout << p[j] << ' ';
        // cout << '\n';

        if (dp[m + 1][0]) {
            cout << "0\n\n";
        } else cout << "-1\n";
    }
    return 0;
}

/*
Hack case:
1
11 3
4 8 10

Answer:
4
4 4 4 10

Hack case:
1
18 8
2 6 9 11 15 16 17 18
*/

Subtask #1
6.0 / 15.0

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

Subtask #2
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is partially correct
2 Correct 7 ms 588 KB Output is partially correct
3 Correct 29 ms 592 KB Output is partially correct
4 Correct 29 ms 676 KB Output is partially correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 588 KB Output is partially correct
2 Correct 4 ms 588 KB Output is partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is partially correct
2 Correct 7 ms 588 KB Output is partially correct
3 Correct 29 ms 592 KB Output is partially correct
4 Correct 29 ms 676 KB Output is partially correct
5 Correct 2 ms 588 KB Output is partially correct
6 Correct 2 ms 588 KB Output is partially correct
7 Correct 2 ms 588 KB Output is partially correct

Subtask #5
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is partially correct
2 Correct 7 ms 588 KB Output is partially correct
3 Correct 29 ms 592 KB Output is partially correct
4 Correct 29 ms 676 KB Output is partially correct
5 Correct 2 ms 588 KB Output is partially correct
6 Correct 2 ms 588 KB Output is partially correct
7 Correct 2 ms 588 KB Output is partially correct
8 Correct 7 ms 716 KB Output is partially correct
9 Correct 8 ms 844 KB Output is partially correct
10 Correct 7 ms 836 KB Output is partially correct
11 Correct 7 ms 844 KB Output is partially correct