#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
bool u[200011];
vector<int> ans;
bool query(vector<int> a){
if(a.size() % 2 != 0) return false;
deque<pair<int, int>> b;
map<int, int> mp;
int c = 0;
int pa = 0;
for(auto v : a){
if(b.empty()) b.push_back({v, ++c}), mp[c]++;
else if(b.back().second != -1 && b.back().fi + 1 == v){
b.push_back({v, c}); mp[c]++;
}else{
b.push_back({v - 1, -1});
b.push_back({v, ++c});
mp[c]++;
}
}
int from = b.size();
while(b.size() >= 3 && b[b.size() - 3].se == b[b.size() - 2].se && b[b.size() - 2].se == b[b.size() - 1].se){
ans.push_back(b[b.size() - 2].fi); pair<int, int> p = b[b.size() - 2];
b.pop_back(); b.pop_back(); b.pop_back(); b.push_back(p); mp[b[b.size() - 1].se] -= 2;
}
while(b.size() >= 1){
// for(auto [x, y] : b) printf("(%d %d) ", x, y); printf("\n");
if(b.front().se == -1){
b.pop_front(); continue;
}
if(b.size() >= 3 && b[0].se == b[1].se && b[1].se == b[2].se) {
ans.push_back(b[1].fi); pair<int, int> p = b[1]; mp[b[0].se]--; mp[b[2].se]--;
b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p);
continue;
}
if(b.size() >= 5 && b[1].se == -1 && b[2].se == b[3].se && b[3].se == b[4].se){
set<int> groups;
if(mp[b[2].se] > 3) goto nxt;
for(int i = 5; i < b.size(); i++) {
if(b[i].se == -1) continue;
if(mp[b[i].se] % 2 == 0) groups.insert(b[i].se);
else break;
}
nxt:;
if(mp[b[2].se] > 3 || groups.size() % 2 == 0){
ans.push_back(b[3].fi); pair<int, int> p0 = b[0], p1 = b[1], p2 = b[3]; mp[b[2].se]--; mp[b[4].se]--;
b.pop_front(); b.pop_front(); b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p2); b.push_front(p1); b.push_front(p0);
}else{
ans.push_back(b[1].fi); pair<int, int> p = b[1]; mp[b[0].se]--; mp[b[2].se]--;
b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p);
}
continue;
}
if(b.size() >= 3 && b[1].se == -1){
ans.push_back(b[1].fi); pair<int, int> p = b[1]; mp[b[0].se]--; mp[b[2].se]--;
b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p);
continue;
}
if(b.size() >= 5 && b[0].se == b[1].se && b[0].se != -1 && b[2].se == -1 && b[3].se == b[4].se && b[3].se != -1){
ans.push_back(b[2].fi); pair<int, int> p1 = b[0], p2 = b[2]; mp[b[1].se]--; mp[b[3].se]--;
b.pop_front(); b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p2); b.push_front(p1);
continue;
}
if(from == b.size()) return false; from = b.size();
}
return true;
}
int n, k;
vector<int> p2;
bool solve(){
cin >> n >> k;
fill(u, u + n + 1, false);
vector<int> p;
for(int i = 0; i < k; i++){
int v; cin >> v; p.push_back(v); u[v] = true;
}
p2 = p;
vector<int> st; int gap = 2;
for(int i = 1; i <= n; i++){
if(!u[i]){
if(gap >= 2) st.push_back(i), gap = 0;
else gap = 0;
}else{
gap++;
}
}
st.push_back(n + 1);
int id = 1;
bool ok = true;
ans.clear();
for(int i = 1; i < st.size(); i++){
vector<int> a;
for(id; id < st[i]; id++){
if(!u[id]) a.push_back(id);
}
ok &= query(a);
}
if(!ok){
cout << -1 << endl;
return false;
}
cout << ans.size() << endl;
for(auto i : ans) cout << i << ' '; cout << endl;
return true;
}
bool solve2(){
deque<vector<int>> dq; vector<int> ori; for(int i = 1; i <= n; i++) ori.push_back(i); dq.push_back(ori); set<vector<int>> s; s.insert(ori);
while(!dq.empty()){
vector<int> v = dq.front(); dq.pop_front();
if(v == p2) return true;
for(int i = 1; i < v.size() - 1; i++){
vector<int> v2;
if(find(p2.begin(), p2.end(), v[i - 1]) != p2.end() || find(p2.begin(), p2.end(), v[i + 1]) != p2.end()){
continue;
}
for(int j = 0; j < v.size(); j++){
if(j != i - 1 && j != i + 1){
v2.push_back(v[j]);
}
}
if(!s.count(v2)) s.insert(v2), dq.push_back(v2);
}
}
return false;
}
int32_t main(){
int t; cin >> t;
while(t--){
bool b1 = solve();
bool b2 = solve2();
assert(b1 == b2);
}
}
Compilation message
del13.cpp: In function 'bool query(std::vector<int>)':
del13.cpp:46:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 5; i < b.size(); i++) {
| ~~^~~~~~~~~~
del13.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | if(from == b.size()) return false; from = b.size();
| ~~~~~^~~~~~~~~~~
del13.cpp:71:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
71 | if(from == b.size()) return false; from = b.size();
| ^~
del13.cpp:71:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
71 | if(from == b.size()) return false; from = b.size();
| ^~~~
del13.cpp:16:9: warning: unused variable 'pa' [-Wunused-variable]
16 | int pa = 0;
| ^~
del13.cpp: In function 'bool solve()':
del13.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 1; i < st.size(); i++){
| ~~^~~~~~~~~~~
del13.cpp:101:13: warning: statement has no effect [-Wunused-value]
101 | for(id; id < st[i]; id++){
| ^~
del13.cpp:112:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
112 | for(auto i : ans) cout << i << ' '; cout << endl;
| ^~~
del13.cpp:112:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
112 | for(auto i : ans) cout << i << ' '; cout << endl;
| ^~~~
del13.cpp: In function 'bool solve2()':
del13.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i = 1; i < v.size() - 1; i++){
| ~~^~~~~~~~~~~~~~
del13.cpp:126:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(int j = 0; j < v.size(); j++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
212 KB |
Output is correct |
| 3 |
Correct |
255 ms |
820 KB |
Output is correct |
| 4 |
Correct |
352 ms |
668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
863 ms |
131072 KB |
Time limit exceeded |
| 2 |
Execution timed out |
937 ms |
131072 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
212 KB |
Output is correct |
| 3 |
Correct |
255 ms |
820 KB |
Output is correct |
| 4 |
Correct |
352 ms |
668 KB |
Output is correct |
| 5 |
Execution timed out |
1073 ms |
32036 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1080 ms |
122772 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1084 ms |
59480 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
212 KB |
Output is correct |
| 3 |
Correct |
255 ms |
820 KB |
Output is correct |
| 4 |
Correct |
352 ms |
668 KB |
Output is correct |
| 5 |
Execution timed out |
1073 ms |
32036 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1080 ms |
122772 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1084 ms |
59480 KB |
Time limit exceeded |
| 8 |
Runtime error |
259 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Execution timed out |
1090 ms |
95980 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1089 ms |
108144 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1079 ms |
116244 KB |
Time limit exceeded |
