This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int p[100001];
bool isolated[100001], 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--) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> p[i];
p[0] = 0, p[m + 1] = n + 1;
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 (p[i - 1] != p[i] - 1 && !isolated[i] && !isolated[i - 1]) {
impossible = true;
break;
}
if (isolated[i]) {
if (isolated[i - 1]) {
if (segs.back()[2] == p[i] - 1)
isolated[i] = false;
else if (isolated[i + 1]) {
int needed = 1 + (p[i] - segs.back()[2]) % 2;
segs.push_back({segs.back()[2] + 1, p[i], min(p[i] + needed, p[i + 1] - 1)});
} else
segs.push_back({segs.back()[2] + 1, p[i], p[i + 1] - 1});
} else {
if (isolated[i + 1]) {
int needed = 1 + (p[i] - p[i - 1]) % 2;
segs.push_back({p[i - 1] + 1, p[i], min(p[i] + needed, p[i + 1] - 1)});
} else
segs.push_back({p[i - 1] + 1, p[i], p[i + 1] - 1});
}
}
}
moves.clear();
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |