Submission #400529

#TimeUsernameProblemLanguageResultExecution timeMemory
400529dolphingarlicDEL13 (info1cup18_del13)C++14
30 / 100
13 ms5200 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...