oj.uz

Submission #400529

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

int p[100002];
bool isolated[100002], impossible;
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;
        isolated[0] = isolated[m + 1] = false;
        for (int i = 1; i <= m; i++) {
            isolated[i] = p[i - 1] != p[i] - 1 && p[i + 1] != p[i] + 1;
        }

        impossible = false;
        if ((n - m) & 1) impossible = true;
        vector<array<int, 3>> segs;
        for (int i = 1; i <= m + 1; i++) {
            if (isolated[i]) {
                if (segs.size() && segs.back()[2] == p[i] - 1) {
                    if (isolated[i + 1])
                        isolated[i] = false;
                    else {
                        segs.back()[2] -= 2;
                        if (segs.back()[1] >= segs.back()[2]) {
                            impossible = true;
                            break;
                        }
                        segs.push_back({segs.back()[2] + 1, p[i], p[i + 1] - 1});
                        if ((segs.back()[2] - segs.back()[0]) & 1)
                            segs.back()[2]--;
                        if (segs.back()[1] >= segs.back()[2]) {
                            impossible = true;
                            break;
                        }
                    }
                } else if (isolated[i - 1]) {
                    segs.push_back({segs.back()[2] + 1, p[i], p[i + 1] - 1});
                    if ((segs.back()[2] - segs.back()[0]) & 1)
                        segs.back()[2]--;
                    if (segs.back()[1] >= segs.back()[2]) {
                        impossible = true;
                        break;
                    }
                } else {
                    segs.push_back({p[i - 1] + 1, p[i], p[i + 1] - 1});
                    if ((segs.back()[2] - segs.back()[0]) & 1)
                        segs.back()[2]--;
                    if (segs.back()[1] >= segs.back()[2]) {
                        impossible = true;
                        break;
                    }
                }
            } else {
                if (p[i] - p[i - 1] > 1 && !isolated[i - 1]) {
                    impossible = true;
                    break;
                }
                if (isolated[i - 1] && p[i] - segs.back()[2] > 1) {
                    impossible = true;
                    break;
                }
            }
        }

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

Subtask #1
15.0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 4 ms 348 KB Output isn't correct
4 Incorrect 4 ms 332 KB Output isn't correct

Subtask #3
15.0 / 15.0

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

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 4 ms 348 KB Output isn't correct
4 Incorrect 4 ms 332 KB Output isn't correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 1 ms 292 KB Output isn't correct
7 Incorrect 1 ms 204 KB Output isn't correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 4 ms 348 KB Output isn't correct
4 Incorrect 4 ms 332 KB Output isn't correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 1 ms 292 KB Output isn't correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Incorrect 9 ms 5072 KB Output isn't correct
9 Incorrect 9 ms 5200 KB Output isn't correct
10 Incorrect 10 ms 3660 KB Output isn't correct
11 Incorrect 13 ms 4116 KB Output isn't correct