oj.uz

Submission #400557

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

int p[100002], prv_parity[100002][3];
bool dp[100002][3];
array<int, 3> prv_seg[100002];
vector<int> moves;

void set_dp(int curr, int p1, int p2) {
    if (dp[curr - 1][p2]) {
        dp[curr][p1] = true;
        prv_parity[curr][p1] = p2;
    }
}

void solve(array<int, 3> seg) {
    if (seg[2] == seg[0]) 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--) {
        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) set_dp(i, 0, 0);
            else set_dp(i, 0, 1 + (p[i] - p[i - 1]) % 2);

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

        if (dp[m + 1][0]) {
            vector<array<int, 3>> segs;
            int parity = 0, boundary;
            for (int i = m + 1; i; i--) {
                if (parity) {
                    if (prv_parity[i][parity]) {
                        segs.push_back({p[i] - parity, p[i], boundary - 1});
                        boundary = p[i] - parity;
                    } else {
                        segs.push_back({p[i - 1] + 1, p[i], boundary - 1});
                        boundary = p[i - 1] + 1;
                    }
                } else boundary = p[i];
                parity = prv_parity[i][parity];
            }

            // for (auto i : segs) {
            //     cout << i[0] << ' ' << i[1] << ' ' << i[2] << " | ";
            // }
            // cout << '\n';

            for (auto i : segs) solve(i);
            cout << moves.size() << '\n';
            while (moves.size()) {
                cout << moves.back() << ' ';
                moves.pop_back();
            }
            cout << '\n';
        } else cout << "-1\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is correct
2 Correct 6 ms 588 KB Output is correct
3 Correct 31 ms 588 KB Output is correct
4 Correct 31 ms 636 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is correct
2 Correct 6 ms 588 KB Output is correct
3 Correct 31 ms 588 KB Output is correct
4 Correct 31 ms 636 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is correct
2 Correct 6 ms 588 KB Output is correct
3 Correct 31 ms 588 KB Output is correct
4 Correct 31 ms 636 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 9 ms 844 KB Output is correct
9 Correct 9 ms 1100 KB Output is correct
10 Correct 9 ms 1228 KB Output is correct
11 Correct 17 ms 5144 KB Output is correct