Submission #2107339

---

Source Code Expand

#include <queue>
#include <vector>
#include <iostream>
using namespace std;
const int inf = 1012345678;
int n, m, s; bool vis[4009];
vector<int> riffle_shuffle(vector<int> v) {
	vector<int> ret(v.size());
	for(int i = 0; i < (int)v.size(); i++) {
		ret[(i * 2) % v.size()] = v[i];
	}
	return ret;
}
int main() {
	cin >> n >> m; s = 2 * n + 1;
	vector<int> p(s);
	for(int i = 0; i < s; i++) cin >> p[i], p[i]--;
	vector<int> b(m);
	for(int i = 0; i < m; i++) cin >> b[i], vis[b[i]] = true;
	vector<vector<int> > dist(2 * s + 1, vector<int>(s, inf));
	queue<int> q1; q1.push(0); dist[0][0] = 0;
	while(!q1.empty()) {
		int u = q1.front(); q1.pop();
		for(int i : b) {
			if(dist[0][(u + i) % s] == inf) {
				dist[0][(u + i) % s] = dist[0][u] + 1;
				q1.push((u + i) % s);
			}
		}
	}
	int ret = inf, sa = (s - p[0]) % s;
	for(int i = 0; i < 2 * s; i++) {
		bool flag = true;
		for(int j = 1; j < s; j++) {
			if((p[j] - p[0] + s) % s != j) flag = false;
		}
		if(flag) ret = min(ret, i + dist[i][sa]);
		vector<int> v;
		for(int j = 0; j < s; j++) {
			if(vis[j] && !vis[(j * 2) % s]) v.push_back((j * 2) % s);
		}
		p = riffle_shuffle(p);
		dist[i + 1] = dist[i];
		for(int pw : v) {
			vis[pw] = true;
			vector<vector<int> > d(s);
			for(int j = 0; j < s; j++) {
				if(dist[i + 1][j] != inf) {
					d[dist[i + 1][j]].push_back(j);
				}
			}
			for(int j = 0; j < s - 1; j++) {
				for(int k : d[j]) {
					if(dist[i + 1][k] != j) continue;
					int nxt = (k + pw) % s;
					if(dist[i + 1][nxt] > dist[i + 1][k] + 1) {
						dist[i + 1][nxt] = dist[i + 1][k] + 1;
						d[dist[i + 1][nxt]].push_back(nxt);
					}
				}
			}
		}
	}
	cout << (ret != inf ? ret : -1) << endl;
	return 0;
}

Submission Info

Judge Result