oj.uz

Submission #364896

# Submission time Handle Problem Language Result Execution time Memory
364896 2021-02-10T11:40:02 Z amunduzbaev DEL13 (info1cup18_del13) C++14
15 / 100
 500 ms 4716 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)];

void bit(int x){
	for(int i=0;i<n;i++) cout<<(x>>i&1); 
	cout<<"\n";
}
/*

1
5 1
3

*/

void solve(int t_case){
	memset(dp, 0, sizeof dp);
	cin>>n>>m;
	for(int i=0;i<m;i++) cin>>a[i];
	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;
						}
					}
				}
			}
		}
	}
	
	
	int tt = 0;
	for(int i=0;i<m;i++) a[i]--, tt |= (1 << a[i]);
	vii res;
	//bit(tt);
	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;
		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 46 ms 2412 KB Output is correct
2 Correct 43 ms 2412 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2412 KB Output is correct
2 Correct 43 ms 2412 KB Output is correct
3 Execution timed out 1057 ms 3820 KB Time limit exceeded
4 Execution timed out 1086 ms 4588 KB Time limit exceeded

Subtask #3
0.0 / 15.0

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

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2412 KB Output is correct
2 Correct 43 ms 2412 KB Output is correct
3 Execution timed out 1057 ms 3820 KB Time limit exceeded
4 Execution timed out 1086 ms 4588 KB Time limit exceeded
5 Runtime error 5 ms 4716 KB Execution killed with signal 11
6 Runtime error 5 ms 4716 KB Execution killed with signal 11
7 Runtime error 5 ms 4716 KB Execution killed with signal 11

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2412 KB Output is correct
2 Correct 43 ms 2412 KB Output is correct
3 Execution timed out 1057 ms 3820 KB Time limit exceeded
4 Execution timed out 1086 ms 4588 KB Time limit exceeded
5 Runtime error 5 ms 4716 KB Execution killed with signal 11
6 Runtime error 5 ms 4716 KB Execution killed with signal 11
7 Runtime error 5 ms 4716 KB Execution killed with signal 11
8 Runtime error 5 ms 4716 KB Execution killed with signal 11
9 Runtime error 5 ms 4716 KB Execution killed with signal 11
10 Runtime error 5 ms 4716 KB Execution killed with signal 11
11 Runtime error 5 ms 4716 KB Execution killed with signal 11