| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 317235 | Seanliu | DEL13 (info1cup18_del13) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
using namespace std;
const int maxN = 20;
int T, N, M, l2[1 << maxN], fromst[1 << maxN], del[1 << maxN];
bool pos[1 << maxN];
void solve(){
cin >> N >> 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]--;
}
pos[(1 << N) - 1] = true;
for(int i = (1 << N) - 1; i; i--){
//cout << "i = " << i << endl;
if(!pos[i]) continue;
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++){
pos[i ^ (1 << wok[j - 1]) ^ (1 << wok[j + 1])] = true;
fromst[i ^ (1 << wok[j - 1]) ^ (1 << wok[j + 1])] = i;
del[i ^ (1 << wok[j - 1]) ^ (1 << wok[j + 1])] = wok[j];
}
}
}
int curst = 0;
for(int x : has) curst ^= (1 << x);
//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;
}
int main(){
for(int i = 0; i < maxN; i++) l2[1 << i] = i;
cin >> T;
while(T--){
solve();
}
}