#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxN = 18;
int T, N, M, l2[1 << maxN], fromst[1 << maxN], del[1 << maxN];
bool pos[1 << maxN];
void solve(){
cin >> M;
vector<int> has, wok;
has.resize(M);
fill(pos, pos + (1 << N), false);
for(int i = 0; i < M; i++){
cin >> has[i];
has[i]--;
}
queue<int> que;
que.push((1 << N) - 1);
pos[(1 << N) - 1] = true;
int curst = 0;
for(int x : has) curst ^= (1 << x);
bool f = false;
while(que.size()){
if(f) break;
int i = que.front();
que.pop();
vector<int>().swap(wok);
int x = i;
while(x){
wok.push_back(l2[(x & -x)]);
x -= (x & -x);
}
//for(int x : wok) cout << x << " ";
//cout << endl;
if(wok.size() >= 3){
for(int j = 1; j < wok.size() - 1; j++){
int n = i ^ (1 << wok[j - 1]) ^ (1 << wok[j + 1]);
if(pos[n] || ((n & curst) != curst)) continue;
pos[n] = true;
que.push(n);
fromst[n] = i;
del[n] = wok[j];
if(n == curst){
f = true;
break;
}
}
}
}
//cout << "curst = " << curst << endl;
if(!pos[curst]){
cout << -1 << endl;
return;
}
vector<int> ans;
vector<int>().swap(ans);
while(curst != ((1 << N) - 1)){
ans.push_back(del[curst]);
curst = fromst[curst];
}
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
for(int x : ans) cout << x + 1 << " ";
cout << endl;
}
void solve2(){
cin >> M;
bool has[100000];
vector<int> ans;
vector<int>().swap(ans);
int x, cnt = 0;
for(int i = 0; i < M; i++){
cin >> x;
x--;
has[x] = true;
cnt++;
}
int k = -1;
for(int i = 1; i < N - 1; i++){
if(has[i] && !has[i - 1] && !has[i + 1]){
k = i;
}
}
if(k == -1 && cnt != N){
cout << -1 << endl;
return;
} else if(k == -1){
cout << 0 << endl;
return;
}
cout << "k = " << k << endl;
deque<int> l, r;
for(int i = k - 1; i >= 0 && !has[i]; i--){
//cout << "i = " << i << endl;
l.push_front(i);
}
for(int i = k + 1; i < N && !has[i]; i++){
//cout << "i = " << i << endl;
r.push_back(i);
}
while(l.size() > 2){
int a = l.front();
l.pop_front();
int b = l.front();
l.pop_front();
int c = l.front();
l.pop_front();
ans.push_back(b);
l.push_front(b);
}
while(r.size() > 2){
int a = r.front();
r.pop_front();
int b = r.front();
r.pop_front();
int c = r.front();
r.pop_front();
ans.push_back(b);
r.push_front(b);
}
if(l.size() != r.size()){
cout << -1 << endl;
}
while(l.size()){
l.pop_back();
r.pop_back();
ans.push_back(k);
}
cout << ans.size() << endl;
for(int x : ans) cout << x << " ";
cout << endl;
}
int main(){
for(int i = 0; i < maxN; i++) l2[1 << i] = i;
cin >> T;
while(T--){
cin >> N;
if(N <= 18)
solve();
else solve2();
}
}
Compilation message
del13.cpp: In function 'void solve()':
del13.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j = 1; j < wok.size() - 1; j++){
| ~~^~~~~~~~~~~~~~~~
del13.cpp: In function 'void solve2()':
del13.cpp:108:7: warning: unused variable 'a' [-Wunused-variable]
108 | int a = l.front();
| ^
del13.cpp:112:7: warning: unused variable 'c' [-Wunused-variable]
112 | int c = l.front();
| ^
del13.cpp:118:7: warning: unused variable 'a' [-Wunused-variable]
118 | int a = r.front();
| ^
del13.cpp:122:7: warning: unused variable 'c' [-Wunused-variable]
122 | int c = r.front();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
239 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
417 ms |
1784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
1920 KB |
Expected integer, but "k" found |
| 2 |
Incorrect |
18 ms |
1464 KB |
Expected integer, but "k" found |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
239 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
417 ms |
1784 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
384 KB |
Expected integer, but "k" found |
| 6 |
Incorrect |
3 ms |
896 KB |
Expected integer, but "k" found |
| 7 |
Incorrect |
3 ms |
384 KB |
Expected integer, but "k" found |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
239 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
417 ms |
1784 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
384 KB |
Expected integer, but "k" found |
| 6 |
Incorrect |
3 ms |
896 KB |
Expected integer, but "k" found |
| 7 |
Incorrect |
3 ms |
384 KB |
Expected integer, but "k" found |
| 8 |
Incorrect |
30 ms |
1276 KB |
Expected integer, but "k" found |
| 9 |
Incorrect |
31 ms |
512 KB |
Expected integer, but "k" found |
| 10 |
Incorrect |
31 ms |
1024 KB |
Expected integer, but "k" found |
| 11 |
Incorrect |
27 ms |
512 KB |
Expected integer, but "k" found |
