Submission #2107435


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);
		}
		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

Submission Time
Task B - 天下一マジック
User square1001
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1699 Byte
Status RE
Exec Time 2115 ms
Memory 129312 KB

Judge Result

Set Name level1 level2 All
Score / Max Score 0 / 20 0 / 80 0 / 100
Status
AC × 7
WA × 9
AC × 11
WA × 24
TLE × 1
AC × 17
WA × 27
TLE × 15
RE × 16
Set Name Test Cases
level1 level1-00, level1-01, level1-02, level1-03, level1-04, level1-05, level1-06, level1-07, level1-08, level1-09, level1-10, level1-11, level1-12, level1-13, level1-14, level1-15
level2 level1-00, level1-01, level1-02, level1-03, level1-04, level1-05, level1-06, level1-07, level1-08, level1-09, level1-10, level1-11, level1-12, level1-13, level1-14, level1-15, level2-00, level2-01, level2-02, level2-03, level2-04, level2-05, level2-06, level2-07, level2-08, level2-09, level2-10, level2-11, level2-12, level2-13, level2-14, level2-15, level2-16, level2-17, level2-18, level2-19
All level1-00, level1-01, level1-02, level1-03, level1-04, level1-05, level1-06, level1-07, level1-08, level1-09, level1-10, level1-11, level1-12, level1-13, level1-14, level1-15, level2-00, level2-01, level2-02, level2-03, level2-04, level2-05, level2-06, level2-07, level2-08, level2-09, level2-10, level2-11, level2-12, level2-13, level2-14, level2-15, level2-16, level2-17, level2-18, level2-19, level3-00, level3-01, level3-02, level3-03, level3-04, level3-05, level3-06, level3-07, level3-08, level3-09, level3-10, level3-11, level3-12, level3-13, level3-14, level3-15, level3-16, level3-17, level3-18, level3-19, level3-20, level3-21, level3-22, level3-23, level3-24, level3-25, level3-26, level3-27, level3-28, level3-29, level3-30, level3-31, level3-32, level3-33, level3-34, level3-35, level3-36, level3-37, level3-38
Case Name Status Exec Time Memory
level1-00 WA 1 ms 256 KB
level1-01 AC 1 ms 256 KB
level1-02 AC 1 ms 256 KB
level1-03 WA 1 ms 256 KB
level1-04 WA 1 ms 256 KB
level1-05 WA 1 ms 256 KB
level1-06 AC 1 ms 256 KB
level1-07 WA 1 ms 256 KB
level1-08 WA 1 ms 256 KB
level1-09 AC 1 ms 256 KB
level1-10 AC 1 ms 256 KB
level1-11 AC 1 ms 256 KB
level1-12 AC 1 ms 256 KB
level1-13 WA 1 ms 256 KB
level1-14 WA 1 ms 256 KB
level1-15 WA 1 ms 256 KB
level2-00 AC 71 ms 4608 KB
level2-01 AC 1919 ms 127360 KB
level2-02 AC 1699 ms 127616 KB
level2-03 AC 1958 ms 127360 KB
level2-04 WA 1885 ms 127360 KB
level2-05 WA 1700 ms 127616 KB
level2-06 WA 1726 ms 127616 KB
level2-07 WA 1886 ms 127360 KB
level2-08 WA 1735 ms 127616 KB
level2-09 WA 1888 ms 127360 KB
level2-10 WA 1995 ms 127360 KB
level2-11 WA 2000 ms 127104 KB
level2-12 WA 1715 ms 127104 KB
level2-13 WA 1715 ms 127616 KB
level2-14 WA 1890 ms 129312 KB
level2-15 WA 1698 ms 127616 KB
level2-16 WA 1888 ms 127360 KB
level2-17 WA 1957 ms 127360 KB
level2-18 WA 1715 ms 127104 KB
level2-19 TLE 2070 ms 126848 KB
level3-00 AC 1 ms 256 KB
level3-01 AC 53 ms 5376 KB
level3-02 TLE 2112 ms 127344 KB
level3-03 TLE 2111 ms 127488 KB
level3-04 AC 859 ms 5376 KB
level3-05 TLE 2111 ms 116028 KB
level3-06 RE 100 ms 256 KB
level3-07 RE 1488 ms -870652 KB
level3-08 RE 1775 ms -870688 KB
level3-09 RE 1824 ms -870048 KB
level3-10 RE 1915 ms -869924 KB
level3-11 WA 1374 ms 129012 KB
level3-12 RE 1608 ms -869772 KB
level3-13 TLE 2114 ms 127348 KB
level3-14 RE 2059 ms -869888 KB
level3-15 TLE 2114 ms 127532 KB
level3-16 TLE 2113 ms 129260 KB
level3-17 TLE 2114 ms 116024 KB
level3-18 TLE 2113 ms 116024 KB
level3-19 TLE 2115 ms 127280 KB
level3-20 TLE 2114 ms 127092 KB
level3-21 WA 1856 ms 126976 KB
level3-22 TLE 2115 ms 127488 KB
level3-23 TLE 2090 ms 129276 KB
level3-24 AC 1534 ms 127488 KB
level3-25 TLE 2114 ms 127232 KB
level3-26 TLE 2114 ms 127232 KB
level3-27 WA 1318 ms 126976 KB
level3-28 RE 1595 ms -869412 KB
level3-29 RE 1678 ms -869408 KB
level3-30 RE 1699 ms -869284 KB
level3-31 RE 1952 ms -869156 KB
level3-32 RE 1979 ms -869412 KB
level3-33 RE 1614 ms -869408 KB
level3-34 RE 1602 ms -869284 KB
level3-35 RE 1683 ms -869412 KB
level3-36 RE 1701 ms -869156 KB
level3-37 AC 11 ms 1780 KB
level3-38 AC 516 ms 108800 KB