#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;
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);
}
while(b.size() >= 1){
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];
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 && !(b.size() >= 7 && b[5].se == -1 && mp[b[6].se] % 2 == 0)){
ans.push_back(b[3].fi); pair<int, int> p0 = b[0], p1 = b[1], p2 = b[3];
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);
continue;
}
if(b.size() >= 3 && b[1].se == -1){
ans.push_back(b[1].fi); pair<int, int> p = b[1];
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];
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);
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;
for(int j = 0; j < v.size(); j++){
if(j != i - 1 && j != i + 1){
v2.push_back(v[j]);
}
}
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:56: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]
56 | if(from == b.size()) return false; from = b.size();
| ~~~~~^~~~~~~~~~~
del13.cpp:56:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
56 | if(from == b.size()) return false; from = b.size();
| ^~
del13.cpp:56:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
56 | if(from == b.size()) return false; from = b.size();
| ^~~~
del13.cpp: In function 'bool solve()':
del13.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 1; i < st.size(); i++){
| ~~^~~~~~~~~~~
del13.cpp:86:13: warning: statement has no effect [-Wunused-value]
86 | for(id; id < st[i]; id++){
| ^~
del13.cpp:97:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
97 | for(auto i : ans) cout << i << ' '; cout << endl;
| ^~~
del13.cpp:97:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
97 | for(auto i : ans) cout << i << ' '; cout << endl;
| ^~~~
del13.cpp: In function 'bool solve2()':
del13.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i = 1; i < v.size() - 1; i++){
| ~~^~~~~~~~~~~~~~
del13.cpp:108:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int j = 0; j < v.size(); j++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
1077 ms |
113304 KB |
Time limit exceeded |
| 4 |
Execution timed out |
706 ms |
131072 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
170 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
309 ms |
131072 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
1077 ms |
113304 KB |
Time limit exceeded |
| 4 |
Execution timed out |
706 ms |
131072 KB |
Time limit exceeded |
| 5 |
Runtime error |
149 ms |
131072 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
155 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
193 ms |
131072 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
1077 ms |
113304 KB |
Time limit exceeded |
| 4 |
Execution timed out |
706 ms |
131072 KB |
Time limit exceeded |
| 5 |
Runtime error |
149 ms |
131072 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
155 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
193 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
155 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
154 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
150 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
166 ms |
131072 KB |
Execution killed with signal 9 |
