#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define MX 5000
#define MAX 5000
vector<int> tree[MAX];
int cnt = 1;
int dep[MAX];
vector<int> cnum = { 3, 3, 3, 3, 3, 3, 2 };
int dv[MAX] = { 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7 };
int pl[MAX] = { 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1 };
int ind[MAX] = { 0, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 };
int vloc[MAX];
pii range[MAX];
int make_tree(int l, int r, int x = 1, int d = 0) {
dep[x] = d;
range[x] = { l, r };
if (r - l <= 1) return x;
int intv = (r - l - 1 + cnum[d] - 1) / cnum[d];
for (int i = 0; i < cnum[d]; i++) {
tree[x].push_back(make_tree(l + i * intv + 1, l + i * intv + intv, ++cnt, d + 1));
vloc[tree[x].back()] = i;
}
return x;
}
bool chk(pii p, int x) {
return p.first <= x && x <= p.second;
}
int find_vertex(int x, int d, int loc = 1) {
if (d == dep[loc]) return loc;
if (x == range[loc].first) return -1;
if (x == range[loc].second) return -2;
for (auto v : tree[loc]) if (chk(range[v], x)) return find_vertex(x, d, v);
}
int calc(int b, int x) {
if (!b) {
int d = b / 3 + 1;
int v = find_vertex(x, 1);
if (v == -1) return -(pl[b] + 1);
if (v == -2) return -(2 - pl[b]);
return vloc[v] + 1;
}
else if (b >= 19) {
int d = b / 3 + 1;
int v = find_vertex(x, d);
if (v == -1) return -(pl[b] + 1);
if (v == -2) return -(2 - pl[b]);
if (vloc[v] == b - 19) {
if (range[v].first == x) return -(pl[b] + 1);
else return -(2 - pl[b]);
}
else {
if (vloc[v] < b - 19) return -(pl[b] + 1);
else return -(2 - pl[b]);
}
}
else {
int d = (b - 1) / 3 + 1;
int rloc = ind[b];
int v = find_vertex(x, d);
if (v == -1) return -(pl[b] + 1);
if (v == -2) return -(2 - pl[b]);
if (vloc[v] == rloc) {
int nv = find_vertex(x, d + 1);
if (nv == -1) return -(pl[b] + 1);
if (nv == -2) return -(2 - pl[b]);
return d * 3 + 1 + vloc[nv];
}
else {
if (vloc[v] < rloc) return -(pl[b] + 1);
else return -(2 - pl[b]);
}
}
}
std::vector<std::vector<int>> devise_strategy(int N) {
make_tree(1, MX);
vector<vector<int>> ans(21, vector<int>(N + 1));
int i, j;
for (i = 0; i <= 20; i++) ans[i][0] = pl[i];
for (i = 0; i <= 20; i++) for (j = 1; j <= N; j++) ans[i][j] = calc(i, j);
return ans;
}
Compilation message
prison.cpp: In function 'int calc(int, int)':
prison.cpp:43:7: warning: unused variable 'd' [-Wunused-variable]
43 | int d = b / 3 + 1;
| ^
prison.cpp: In function 'int find_vertex(int, int, int)':
prison.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
39 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
440 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
436 KB |
Output is correct |
2 |
Correct |
1 ms |
472 KB |
Output is correct |
3 |
Correct |
1 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
436 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
7 ms |
768 KB |
Output is correct |
5 |
Correct |
12 ms |
1080 KB |
Output is correct |
6 |
Correct |
15 ms |
1108 KB |
Output is correct |
7 |
Correct |
14 ms |
1236 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
6 ms |
724 KB |
Output is correct |
12 |
Correct |
12 ms |
1024 KB |
Output is correct |