#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;
}
int32_t main(){
int t; cin >> t;
while(t--){
bool b1 = solve();
}
}
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 'int32_t main()':
del13.cpp:104:14: warning: unused variable 'b1' [-Wunused-variable]
104 | bool b1 = solve();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
360 KB |
Output isn't correct |
| 4 |
Incorrect |
12 ms |
340 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
596 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
360 KB |
Output isn't correct |
| 4 |
Incorrect |
12 ms |
340 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
312 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
360 KB |
Output isn't correct |
| 4 |
Incorrect |
12 ms |
340 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
312 KB |
Output isn't correct |
| 8 |
Incorrect |
15 ms |
1484 KB |
Output isn't correct |
| 9 |
Incorrect |
21 ms |
1604 KB |
Output isn't correct |
| 10 |
Incorrect |
17 ms |
1228 KB |
Output isn't correct |
| 11 |
Incorrect |
21 ms |
2244 KB |
Output isn't correct |
