#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vi> vvi;
typedef pair<double, double> dodo;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
int N, M;
bool arr[100000];
void next_zero(int &p) {
while (p < N && arr[p]) p++;
}
void next_one(int &p) {
while (p < N && !arr[p]) p++;
}
vi instructions;
bool process(ii interval) {
vi group_sz(1), group_bgn(1);
int ptr = interval.first;
group_bgn[0] = ptr;
bool type = false;
while (ptr <= interval.second) {
if (arr[ptr] == type) {
group_sz[group_sz.size()-1]++;
} else {
type = arr[ptr];
group_sz.pb(1);
group_bgn.pb(ptr);
}
ptr++;
}
/*for (int i = 0; i < group_sz.size(); i++) {
cerr << "g" << i << " sz: " << group_sz[i] << " bgn: " << group_bgn[i] << endl;
}*/
bool flag = true;
vi tmp;
for (int i = 0; i < group_sz.size(); i += 2) tmp.pb(group_sz[i]);
vi mn(tmp.size()), mx(tmp.size());
for (int i = 0; i < tmp.size(); i++) mn[i] = mx[i] = tmp[i];
for (int i = 0; i < tmp.size()-1; i++) {
if (tmp[i] >= 4 && tmp[i] % 2 == 0) mn[i] -= (tmp[i] - 2);
if (tmp[i] >= 3 && tmp[i] % 2 == 1) mn[i] -= (tmp[i] - 1);
if (mn[i] > 0) {
if (mn[i] <= mx[i+1]) {
int t = mn[i];
mn[i] -= mx[i+1];
mx[i+1] -= t;
mn[i+1] -= mx[i];
} else {
flag = false;
break;
}
}
else if (mx[i] >= 0) {
mn[i+1] -= mx[i];
}
else {
flag = false;
break;
}
}
if (tmp[tmp.size()-1] >= 4 && tmp[tmp.size()-1] % 2 == 0) mn[tmp.size()-1] -= (tmp[tmp.size()-1] - 2);
if (tmp[tmp.size()-1] >= 3 && tmp[tmp.size()-1] % 2 == 1) mn[tmp.size()-1] -= (tmp[tmp.size()-1] - 1);
if (mn[tmp.size()-1] > 0) flag = false;
if (mx[tmp.size()-1] < 0) flag = false;
/*cerr << "tmprange: ";
for (int i = 0; i < tmp.size(); i++) cerr << tmp[i] << " ";
cerr << endl;
cerr << "maxrange: ";
for (int i = 0; i < tmp.size(); i++) cerr << mx[i] << " ";
cerr << endl;
cerr << "minrange: ";
for (int i = 0; i < tmp.size(); i++) cerr << mn[i] << " ";
cerr << endl;*/
return flag;
}
int main(int argc, char **argv) {
ios_base::sync_with_stdio(0);
cin.tie(0);
int TC; cin >> TC;
while (TC--) {
cin >> N >> M;
memset(arr, 0, sizeof(arr));
for (int i = 0; i < M; i++) {
int x; cin >> x; x--; arr[x] = true;
}
int ptr = 0;
vii intervals;
while (true) {
ii interval;
next_zero(ptr);
if (ptr == N) break;
interval.first = ptr;
while (true) {
next_one(ptr);
if (ptr >= N-1 || arr[ptr+1]) {
interval.second = ptr-1;
break;
}
ptr++;
}
intervals.pb(interval);
if (ptr == N) break;
}
/*for (int i = 0; i < intervals.size(); i++) {
cerr << "interval " << i << ": " << intervals[i].first << "-" << intervals[i].second << endl;
}*/
instructions.clear();
bool flag = true;
for (int i = 0; i < intervals.size(); i++) {
flag &= process(intervals[i]);
if (!flag) break;
}
if (flag) {
cout << instructions.size() << '\n';
for (int i = 0; i < instructions.size(); i++) {
cout << instructions[i] << " ";
}
cout << '\n';
} else {
cout << -1 << '\n';
}
}
return 0;
}
Compilation message
del13.cpp: In function 'bool process(ii)':
del13.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < group_sz.size(); i += 2) tmp.pb(group_sz[i]);
~~^~~~~~~~~~~~~~~~~
del13.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tmp.size(); i++) mn[i] = mx[i] = tmp[i];
~~^~~~~~~~~~~~
del13.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tmp.size()-1; i++) {
~~^~~~~~~~~~~~~~
del13.cpp: In function 'int main(int, char**)':
del13.cpp:119:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < intervals.size(); i++) {
~~^~~~~~~~~~~~~~~~~~
del13.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < instructions.size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
616 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
616 KB |
Output isn't correct |
| 3 |
Incorrect |
22 ms |
616 KB |
Output isn't correct |
| 4 |
Incorrect |
20 ms |
672 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
672 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
672 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
616 KB |
Output isn't correct |
| 3 |
Incorrect |
22 ms |
616 KB |
Output isn't correct |
| 4 |
Incorrect |
20 ms |
672 KB |
Output isn't correct |
| 5 |
Partially correct |
3 ms |
672 KB |
Output is partially correct |
| 6 |
Partially correct |
3 ms |
672 KB |
Output is partially correct |
| 7 |
Partially correct |
3 ms |
672 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
616 KB |
Output isn't correct |
| 3 |
Incorrect |
22 ms |
616 KB |
Output isn't correct |
| 4 |
Incorrect |
20 ms |
672 KB |
Output isn't correct |
| 5 |
Partially correct |
3 ms |
672 KB |
Output is partially correct |
| 6 |
Partially correct |
3 ms |
672 KB |
Output is partially correct |
| 7 |
Partially correct |
3 ms |
672 KB |
Output is partially correct |
| 8 |
Incorrect |
15 ms |
672 KB |
Output isn't correct |
| 9 |
Incorrect |
14 ms |
716 KB |
Output isn't correct |
| 10 |
Incorrect |
13 ms |
796 KB |
Output isn't correct |
| 11 |
Partially correct |
15 ms |
796 KB |
Output is partially correct |
