Submission #2107443

---

Source Code Expand

#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int n, m, s, inf = 1012345678; bool vis[4009];
vector<int> riffle_shuffle(vector<int> p) {
	int sz = p.size();
	vector<int> ret(sz);
	for(int i = 0; i < sz; i++) ret[i * 2 % sz] = p[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> val;
		for(int j = 0; j < s; j++) {
			if(vis[j] && !vis[j * 2 % s]) val.push_back(j * 2 % s);
		}
		for(int j : val) vis[j] = true;
		p = riffle_shuffle(p);
		vector<vector<int> > d(s);
		for(int j = 0; j < s; j++) {
			if(dist[i][j] != inf) {
				d[dist[i][j]].push_back(j);
				dist[i + 1][j] = dist[i][j];
			}
		}
		for(int j = 0; j < s - 1; j++) {
			for(int k : d[j]) {
				if(dist[i + 1][k] != j) continue;
				for(int l : val) {
					int nxt = (k + l) % 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