| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 360049 |
2021-01-27T12:26:05 Z |
Mlxa |
DEL13 (info1cup18_del13) |
C++14 |
|
500 ms |
28988 KB |
#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
const int N = 1e6 + 10;
int dp[N][3];
struct group {
int l;
int r;
int k;
group(int a, int b) : l(a), r(b), k(b - a + 1) {}
};
vector<group> g;
vector<int> sub(vector<int> a) {
// cout << "sub" << endl;
// for (int e : a) {
// cout << e;
// }
// cout << endl << endl;
int n = (int)a.size();
fill_n(dp[0], 3 * N, -1);
int i = 0;
g.clear();
while (i < n) {
if (!a[i]) {
++i;
continue;
}
int l = i;
while (i + 1 < n && a[i + 1]) {
++i;
}
g.emplace_back(l, i);
++i;
}
assert(g.size());
int m = (int)g.size();
// cout << "m = " << m << endl;
// for (auto e : g) {
// cout << e.l + 1 << " " << e.r + 1 << endl;
// }
// cout << "---" << endl;
for (int least = 1; least <= 2; ++least) {
int take = g[0].k - least;
if (take < 0 || take % 2) {
continue;
}
dp[0][least] = take / 2;
}
for (i = 1; i < m; ++i) {
for (int pr = 0; pr <= 2 && pr <= g[i].k; ++pr) {
if (dp[i - 1][pr] == -1) {
continue;
}
int fw = g[i].k - pr;
if (!fw) {
fw = 0;
} else if (fw % 2) {
fw = 1;
} else {
fw = 2;
}
int take = g[i].k - pr - fw;
assert(take % 2 == 0);
dp[i][fw] = take / 2;
if (pr > 0 && fw == 2) {
fw = 0;
take = g[i].k - pr - fw;
assert(take % 2 == 0);
dp[i][fw] = take / 2;
}
}
}
vector<pair<int, int>> num;
for (i = 0; i < n; ++i) {
num.emplace_back(i, a[i]);
}
i = m - 1;
int j = 0;
if (dp[i][j] == -1) {
return {};
}
vector<int> local;
vector<int> byg;
while (i >= 0) {
byg.push_back(dp[i][j]);
j = g[i].k - j - 2 * dp[i][j];
--i;
assert(0 <= j && j < 3);
}
reverse(all(byg));
assert((int)byg.size() == m);
for (i = 0; i < m; ++i) {
while (byg[i]--) {
auto it = lower_bound(all(num), mp(g[i].l, -1LL));
assert(it < num.end() && it->x <= g[i].r && it->y == 1);
auto nx = it + 1;
assert(nx < num.end() && nx->x <= g[i].r && nx->y == 1);
auto nnx = nx + 1;
assert(nnx < num.end() && nnx->x <= g[i].r && nnx->y == 1);
local.push_back(nx->x);
num.erase(nnx);
num.erase(it);
}
}
while (num.size()) {
int cnt = 0;
while (num.size() && num.back().y) {
++cnt;
num.pop_back();
}
assert(num.size() && num.back().y == 0);
int mid = num.back().x;
num.pop_back();
while (cnt--) {
local.push_back(mid);
assert(num.size() && num.back().y == 1);
num.pop_back();
}
}
return local;
}
vector<int> a, answer;
bool segment(int l, int r) {
assert(0 <= l && l <= r && r < (int)a.size());
vector<int> cur(a.begin() + l, a.begin() + r + 1);
if (!count(all(cur), 1)) {
return true;
}
vector<int> tmp = sub(cur);
if (!tmp.size()) {
return false;
}
for (int e : tmp) {
answer.push_back(e + l + 1);
}
return true;
}
void solve() {
int n, q;
cin >> n >> q;
a.assign(n, 1);
for (int x; q--; ) {
cin >> x;
--x;
a[x] = 0;
}
answer.clear();
int to = n - 1;
for (int from = n - 3; from >= 0; --from) {
if (from + 1 < (int)a.size() && from + 2 <= to && !a[from] && !a[from + 1]) {
if (!segment(from + 2, to)) {
cout << "-1\n";
return;
}
to = from - 1;
}
}
if (0 <= to) {
segment(0, to);
}
cout << answer.size() << "\n";
for (int e : answer) {
cout << e << " ";
}
cout << "\n";
}
signed main() {
#ifdef LC
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(0); cin.tie(0);
int tn;
cin >> tn;
while (tn--) {
solve();
}
// int n;
// cin >> n;
// a.resize(n);
// for (int &e : a) {
// cin >> e;
// }
// auto e = sub(a);
// cout << e.size() << endl;
// for (int elem : e) {
// cout << elem + 1 << " ";
// }
// cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1041 ms |
23788 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1083 ms |
23832 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1041 ms |
23788 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1083 ms |
23832 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1097 ms |
23916 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1087 ms |
23916 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1052 ms |
24332 KB |
Time limit exceeded |
| 2 |
Execution timed out |
676 ms |
28988 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1041 ms |
23788 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1083 ms |
23832 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1097 ms |
23916 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1087 ms |
23916 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1084 ms |
23916 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1025 ms |
24048 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1090 ms |
23788 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1041 ms |
23788 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1083 ms |
23832 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1097 ms |
23916 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1087 ms |
23916 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1084 ms |
23916 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1025 ms |
24048 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1090 ms |
23788 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1097 ms |
24044 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1085 ms |
24300 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1101 ms |
28260 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1089 ms |
28268 KB |
Time limit exceeded |
