Submission #2107437
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); } 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
Submission Time | |
---|---|
Task | B - 天下一マジック |
User | square1001 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1734 Byte |
Status | RE |
Exec Time | 2530 ms |
Memory | 128884 KB |
Judge Result
Set Name | level1 | level2 | All | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 20 | 0 / 80 | 0 / 100 | ||||||||||||||||
Status |
|
|
|
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 | 70 ms | 4608 KB |
level2-01 | AC | 71 ms | 127232 KB |
level2-02 | AC | 70 ms | 127360 KB |
level2-03 | WA | 71 ms | 127104 KB |
level2-04 | WA | 70 ms | 127232 KB |
level2-05 | WA | 70 ms | 127360 KB |
level2-06 | WA | 70 ms | 127360 KB |
level2-07 | WA | 70 ms | 127232 KB |
level2-08 | WA | 70 ms | 127360 KB |
level2-09 | WA | 70 ms | 127232 KB |
level2-10 | WA | 70 ms | 127104 KB |
level2-11 | WA | 70 ms | 126976 KB |
level2-12 | WA | 71 ms | 126848 KB |
level2-13 | WA | 70 ms | 127360 KB |
level2-14 | WA | 70 ms | 127232 KB |
level2-15 | WA | 70 ms | 127360 KB |
level2-16 | WA | 70 ms | 127232 KB |
level2-17 | WA | 69 ms | 127104 KB |
level2-18 | WA | 70 ms | 126848 KB |
level2-19 | WA | 70 ms | 126720 KB |
level3-00 | AC | 1 ms | 256 KB |
level3-01 | AC | 52 ms | 5376 KB |
level3-02 | AC | 69 ms | 127232 KB |
level3-03 | AC | 70 ms | 127360 KB |
level3-04 | AC | 856 ms | 5376 KB |
level3-05 | TLE | 2111 ms | 116024 KB |
level3-06 | RE | 99 ms | 256 KB |
level3-07 | RE | 2080 ms | -876428 KB |
level3-08 | RE | 1665 ms | -870308 KB |
level3-09 | RE | 1649 ms | -869924 KB |
level3-10 | RE | 1908 ms | -870052 KB |
level3-11 | RE | 476 ms | 128884 KB |
level3-12 | TLE | 2530 ms | -869104 KB |
level3-13 | AC | 88 ms | 128628 KB |
level3-14 | RE | 1524 ms | -869248 KB |
level3-15 | WA | 84 ms | 128756 KB |
level3-16 | WA | 73 ms | 127232 KB |
level3-17 | TLE | 2113 ms | 116024 KB |
level3-18 | TLE | 2112 ms | 118064 KB |
level3-19 | WA | 74 ms | 127104 KB |
level3-20 | WA | 75 ms | 126976 KB |
level3-21 | WA | 73 ms | 126848 KB |
level3-22 | WA | 73 ms | 127360 KB |
level3-23 | WA | 73 ms | 127232 KB |
level3-24 | WA | 73 ms | 127360 KB |
level3-25 | WA | 74 ms | 127232 KB |
level3-26 | WA | 73 ms | 127104 KB |
level3-27 | WA | 73 ms | 126848 KB |
level3-28 | RE | 1947 ms | -869156 KB |
level3-29 | RE | 1829 ms | -869156 KB |
level3-30 | RE | 2018 ms | -869148 KB |
level3-31 | RE | 1624 ms | -869284 KB |
level3-32 | RE | 1516 ms | -869028 KB |
level3-33 | TLE | 2511 ms | -869028 KB |
level3-34 | TLE | 2211 ms | -868900 KB |
level3-35 | RE | 2083 ms | -868900 KB |
level3-36 | RE | 1527 ms | -868772 KB |
level3-37 | AC | 12 ms | 1780 KB |
level3-38 | AC | 514 ms | 108800 KB |