#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> devise_strategy(int n) {
///ios::sync_with_stdio(0); cin.tie(0);
vector<int> dp(n + 1), par(n + 1, 0);
for (int i = 0; i <= n; i++) {
if (i <= 2) {
dp[i] = 0;
continue;
}
dp[i] = i;
for (int j = 1; j <= (i - 2); j++) {
dp[i] = min(dp[i], dp[j] + ((i - 2 + j - 1) / j));
if (dp[j] + ((i - 2 + j - 1) / j) == dp[i]) {
par[i] = j;
}
}
assert(par[i]);
}
int x = dp[n];
vector<int> dims;
vector<vector<int>> what(x + 1, vector<int> (n + 1, 0));
{
int current = n;
while (current >= 3) {
dims.push_back(current);
current = par[current];
}
dims.push_back(current);
///reverse(dims.begin(), dims.end());
}
/// cout << "dims = ";
/**for (int i = 0; i + 1 < (int) dims.size(); i++) {
cout << i << " ---> " << dims[i] << " " << par[dims[i]] << " " << ((dims[i] - 2 + dims[i + 1] - 1) / (dims[i + 1])) << "\n";
}
exit(0);**/
{
int sum_test = 0;
for (int i = 0; i + 1 < (int) dims.size(); i++) {
sum_test += ((dims[i] - 2 + dims[i + 1] - 1) / (dims[i + 1]));
}
assert(sum_test == x);
}
vector<int> position(x + 1, 0);
map<int, int> child;
int current = 0;
position[current++] = 0;
for (int i = 0; i + 1 < (int) dims.size(); i++) {
int now_len = dims[i];
int new_len = dims[i + 1];
int times = ((now_len - 2) + (new_len - 1)) / (new_len);
for (int j = 1; j <= times; j++) {
position[current++] = i + 1;
}
}
for (int i = 0; i <= x; i++) {
///cout << i << " : " << position[i] << "\n";
}
///exit(0);
function<void(int, int, int, int)> dfs = [&] (int state, int turn, int l, int r) {
if (l > r) {
/// return;
}
what[state][0] = turn;
/// cout << "label = " << state << ", ch = " << (char) (turn + 'A') << ", l = " << l << ", r = " << r << "\n";
/** if (turn == 1) {
for (int j = 1; j <= n; j++) {
if (j < l) {
what[state][j] = -2;
}
if (j > r) {
what[state][j] = -1;
}
}
} else {
for (int j = 1; j <= n; j++) {
if (j < l) {
what[state][j] = -1;
}
if (j > r) {
what[state][j] = -2;
}
}
}**/
if (!(l + 1 <= r)) {
return;
}
///cout << state << " " << turn << " : " << l << " " << r << "\n";
assert(l + 1 <= r);
assert(turn == 0 || turn == 1);
assert(0 <= state && state <= x);
assert(0 <= position[state] && position[state] <= (int) dims.size());
assert(r - l + 1 <= dims[position[state]]);
if (turn == 0) {
what[state][l] = -1;
what[state][r] = -2;
} else {
what[state][l] = -2;
what[state][r] = -1;
}
if (l + 1 <= r - 1) {
int st = l + 1, dr = r - 1;
assert(position[state] + 1 < (int) dims.size());
int last = state;
while (last + 1 < (int) position.size() && position[last + 1] == position[last]) {
last++;
}
int now_len = dims[position[state]];
int new_len = dims[position[state] + 1];
int times = ((now_len - 2) + (new_len - 1)) / (new_len);
vector<vector<int>> guys;
vector<int> states;
for (int iter = 1; iter <= times; iter++) {
int l2 = st, r2 = min(dr, st + new_len - 1);
assert(position[last + iter] == position[state] + 1);
guys.push_back({});
states.push_back(last + iter);
for (int num = l2; num <= r2; num++) {
what[state][num] = last + iter;
guys.back().push_back(num);
}
dfs(last + iter, turn ^ 1, l2, r2);
st = r2 + 1;
}
for (int i0 = 0; i0 < (int) guys.size(); i0++) {
///cout << " = " << states[i0] << "\n";
if (turn == 1) {
what[states[i0]][l] = -1;
what[states[i0]][r] = -2;
} else {
what[states[i0]][l] = -2;
what[states[i0]][r] = -1;
}
///what[states[i0]][l] = (turn ^ 1);
///what[states[i0]][r] = (turn ^ 1 ^ 1);
///what[states[i0]][l] ^= 1, what[states[i0]][r] ^= 1;
for (int i1 = 0; i1 < (int) guys.size(); i1++) {
if (i0 == i1) continue;
int who = (i0 < i1) ^ turn ^ 1;
assert(who == 0 || who == 1);
for (auto &yy : guys[i1]) {
if (who == 0) {
what[states[i0]][yy] = -1;
} else {
what[states[i0]][yy] = -2;
}
}
}
}
assert(st == dr + 1);
}
};
dfs(0, 0, 1, n);
return what;
for (int num = 0; num <= x; num++) {
}
assert(current == x + 1);
/// cout << "\n";
/// exit(0);
for (int i = 0; i <= x; i++) {
/// cout << i << " : " << position[i] << "\n";
/// cout << i << " ---> " << sum[i] << " " << position[i] << "\n";
}
///exit(0);
/// la inceput ce fac? citesc A-ul
/** int sum = 0;
what[0][0] = 0;
for (int val_a = 1; val_a <= n; val_a++) {
if (val_a == 1) {
what[0][val_a] = -1;
continue;
}
if (val_a == n) {
what[0][val_a] = -2;
continue;
}
int j = dims[1];
int delta_val_a = val_a - (2);
int id = delta_val_a / j;
what[0][val_a] = sum + 1 + id;
}*/
return what;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
300 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
17 ms |
564 KB |
Output is correct |
| 5 |
Correct |
51 ms |
836 KB |
Output is correct |
| 6 |
Correct |
71 ms |
968 KB |
Output is correct |
| 7 |
Correct |
73 ms |
1028 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
2 ms |
340 KB |
Output is correct |
| 11 |
Correct |
15 ms |
572 KB |
Output is correct |
| 12 |
Correct |
52 ms |
816 KB |
Output is correct |
