oj.uz

Submission #364898

# Submission time Handle Problem Language Result Execution time Memory
364898 2021-02-10T11:45:30 Z amunduzbaev DEL13 (info1cup18_del13) C++14
30 / 100
 30 ms 3564 KB 
/** 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 15 ms 2156 KB Output is correct
4 Correct 30 ms 3564 KB Output is correct

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Runtime error 1 ms 492 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 15 ms 2156 KB Output is correct
4 Correct 30 ms 3564 KB Output is correct
5 Runtime error 2 ms 492 KB Execution killed with signal 11
6 Runtime error 2 ms 492 KB Execution killed with signal 11
7 Runtime error 1 ms 492 KB Execution killed with signal 11

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 15 ms 2156 KB Output is correct
4 Correct 30 ms 3564 KB Output is correct
5 Runtime error 2 ms 492 KB Execution killed with signal 11
6 Runtime error 2 ms 492 KB Execution killed with signal 11
7 Runtime error 1 ms 492 KB Execution killed with signal 11
8 Runtime error 2 ms 492 KB Execution killed with signal 11
9 Runtime error 2 ms 492 KB Execution killed with signal 11
10 Runtime error 2 ms 492 KB Execution killed with signal 11
11 Runtime error 2 ms 492 KB Execution killed with signal 11