Submission #364898

#	Time	Username	Problem	Language	Result	Execution time	Memory
364898		amunduzbaev	DEL13 (info1cup18_del13)	C++14	30 / 100	30 ms	3564 KiB

del13

/** made by amunduzbaev **/
#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

#define MULTI 1

int n, m, k, ans, res, a[N]; 
int dp[(1<<18)];
pair<int, pii> par[(1<<18)];

/*

1
5 1
3

*/

void solve(int t_case){
	if(t_case > 1) cin>>n; 
	cin>>m;
	for(int i=0;i<m;i++) cin>>a[i];
	int tt = 0;
	for(int i=0;i<m;i++) a[i]--, tt |= (1 << a[i]);
	vii res;
	if(!dp[tt]){
		cout<<"-1\n";
		return;
	}
	while(tt != (1<<n)-1){
		pii cur = par[tt].ss;
		res.pb(par[tt].ff+1);
		tt = tt^(1<<cur.ff)^(1<<cur.ss);
	}
	cout<<sz(res)<<"\n";
	for(int i=sz(res)-1;i>=0;i--) cout<<res[i]<<" ";
	cout<<"\n";
}



signed main(){
	NeedForSpeed
	
	if(!MULTI) {
		solve(1);
	} else {
		int t; cin>>t;
		cin>>n;
		dp[(1<<n)-1] = 1;
		for(int i=(1<<n)-1;i>=0;i--){
			for(int j=1;j<n-1;j++){
				if(i >> j&1 && !(i >> (j-1)&1) && !(i >> (j+1)&1)){
					bool ok = 0;
					for(int l=j-1;!ok && l>=0 && !(i>>l&1);l--){
						for(int r=j+1;!ok && r<n && !(i>>r&1);r++){
							int tt = i^(1<<(l))^(1<<(r));
							if(dp[tt]){
								dp[i] = dp[tt];
								par[i] = {j, {l, r}};
								ok = 1;
							}
						}
					}
				}
			}
		}
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	}
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30