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 <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int inf = 1'000'000'088;
template<typename T>
T& InplaceMin(T& a, const T& b) {
return a = min(a, b);
}
void Solve(istream& in, ostream& out) {
int n, q;
in >> n >> q;
vector<int> p(q + 2);
p[q + 1] = n + 1;
for (int i = 1; i <= q; ++i) {
in >> p[i];
}
vector<vector<pair<int, int>>> dp(q + 2, vector<pair<int, int>>(3, make_pair(inf, inf)));
function<pair<int, int>(int, int, int, int)> update =
[&dp](int i, int from, int to, int delta) {
return InplaceMin(dp[i + 1][to], make_pair(dp[i][from].first + delta, from));
};
dp[0][0].first = 0;
for (int i = 0; i <= q; ++i) {
int cnt = p[i + 1] - p[i] - 1;
for (int j = 0; j <= min(cnt, 2); j++) {
if (dp[i][j].first == inf) {
continue;
}
if (cnt == j) {
update(i, j, 0, 0);
continue;
}
if ((j + cnt) % 2 == 0) {
if (j != 0) {
update(i, j, 0, (cnt - j) / 2);
}
update(i, j, 2, (cnt - j) / 2 + 1);
} else {
update(i, j, 1, (cnt - j) / 2 + 1);
}
}
}
if (dp[q + 1][0].first == inf) {
out << -1 << endl;
return;
}
vector<int> ans;
int cur = 0;
for (int i = q; i >= 0; --i) {
int prev = dp[i + 1][cur].second;
int first = p[i] + 2 + prev;
if (cur == 0) {
for (int j = 0; j < prev; ++j) {
ans.push_back(p[i]);
}
first -= prev;
}
for (int j = first; j + 1 < p[i + 1]; j += 2) {
ans.push_back(j);
}
if (cur != 0) {
for (int j = 0; j < prev; ++j) {
ans.push_back(p[i]);
}
}
cur = prev;
}
reverse(ans.begin(), ans.end());
out << ans.size() << endl;
for (auto& item : ans) {
out << item << " ";
}
out << endl;
}
int main() {
std::ios_base::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
Solve(cin, cout);
}
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... |