#include "prison.h"
#include <vector>
using namespace std;
int X = 0;
void findx(int st, int ed, int v) {
if (ed - st == 0) {
X = max(X, v);
return;
}
if (ed - st == 1) {
X = max(X, v);
return;
}
if (ed - st == 2) {
X = max(X, ((v+2)/3)*3 + 1);
return;
}
if (ed - st == 3) {
X = max(X, ((v+2)/3)*3 + 1);
return;
}
if (ed - st == 4) {
X = max(X, ((v+2)/3)*3 + 2);
return;
}
if (ed - st == 5) {
X = max(X, ((v+2)/3)*3 + 2);
return;
}
else {
int x = st + (ed - st) / 3, y = st + ((ed - st) / 3) * 2;
findx(st + 1, x, ((v+2)/3)*3 + 1);
findx(x + 1, y, ((v+2)/3)*3 + 2);
findx(y + 1, ed - 1, ((v+2)/3)*3 + 3);
}
}
void solve(vector< vector<int> > &ans, int st, int ed, int v, int bef) {
int now;
if (bef == -2) now = -1;
else now = -2;
if (ed - st == 0) {
ans[v][0] = (-1 - now);
ans[v][st + 0] = (now);
return;
}
if (ed - st == 1) {
ans[v][0] = (-1 - now);
ans[v][st + 0] = (now);
ans[v][st + 1] = (bef);
return;
}
if (ed - st == 2) {
ans[v][0] = (-1 - now);
ans[v][st + 0] = (now);
ans[v][st + 1] = (((v+2)/3)*3 + 1);
ans[v][st + 2] = (bef);
ans[((v+2)/3)*3 + 1][0] = (-1 - bef);
ans[((v+2)/3)*3 + 1][st + 0] = (bef);
ans[((v+2)/3)*3 + 1][st + 1] = (bef);
ans[((v+2)/3)*3 + 1][st + 2] = (now);
return;
}
if (ed - st == 3) {
ans[v][0] = (-1 - now);
ans[v][st + 0] = (now);
ans[v][st + 1] = (((v+2)/3)*3 + 1);
ans[v][st + 2] = (((v+2)/3)*3 + 1);
ans[v][st + 3] = (bef);
ans[((v+2)/3)*3 + 1][0] = (-1 - bef);
ans[((v+2)/3)*3 + 1][st + 0] = (bef);
ans[((v+2)/3)*3 + 1][st + 1] = (bef);
ans[((v+2)/3)*3 + 1][st + 2] = (now);
ans[((v+2)/3)*3 + 1][st + 3] = (now);
return;
}
if (ed - st == 4) {
ans[v][0] = (-1 - now);
ans[v][st + 0] = (now);
ans[v][st + 1] = (((v+2)/3)*3 + 1);
ans[v][st + 2] = (((v+2)/3)*3 + 1);
ans[v][st + 3] = (((v+2)/3)*3 + 2);
ans[v][st + 4] = (bef);
ans[((v+2)/3)*3 + 1][0] = (-1 - bef);
ans[((v+2)/3)*3 + 1][st + 0] = (bef);
ans[((v+2)/3)*3 + 1][st + 1] = (bef);
ans[((v+2)/3)*3 + 1][st + 2] = (now);
ans[((v+2)/3)*3 + 1][st + 3] = (now);
ans[((v+2)/3)*3 + 1][st + 4] = (now);
ans[((v+2)/3)*3 + 2][0] = (-1 - bef);
ans[((v+2)/3)*3 + 2][st + 0] = (bef);
ans[((v+2)/3)*3 + 2][st + 1] = (bef);
ans[((v+2)/3)*3 + 2][st + 2] = (bef);
ans[((v+2)/3)*3 + 2][st + 3] = (bef);
ans[((v+2)/3)*3 + 2][st + 4] = (now);
return;
}
if (ed - st == 5) {
ans[v][0] = (-1 - now);
ans[v][st + 0] = (now);
ans[v][st + 1] = (((v+2)/3)*3 + 1);
ans[v][st + 2] = (((v+2)/3)*3 + 1);
ans[v][st + 3] = (((v+2)/3)*3 + 2);
ans[v][st + 4] = (((v+2)/3)*3 + 2);
ans[v][st + 5] = (bef);
ans[((v+2)/3)*3 + 1][0] = (-1 - bef);
ans[((v+2)/3)*3 + 1][st + 0] = (bef);
ans[((v+2)/3)*3 + 1][st + 1] = (bef);
ans[((v+2)/3)*3 + 1][st + 2] = (now);
ans[((v+2)/3)*3 + 1][st + 3] = (now);
ans[((v+2)/3)*3 + 1][st + 4] = (now);
ans[((v+2)/3)*3 + 1][st + 5] = (now);
ans[((v+2)/3)*3 + 2][0] = (-1 - bef);
ans[((v+2)/3)*3 + 2][st + 0] = (bef);
ans[((v+2)/3)*3 + 2][st + 1] = (bef);
ans[((v+2)/3)*3 + 2][st + 2] = (bef);
ans[((v+2)/3)*3 + 2][st + 3] = (bef);
ans[((v+2)/3)*3 + 2][st + 4] = (now);
ans[((v+2)/3)*3 + 2][st + 5] = (now);
return;
}
else {
ans[v][0] = (-1 - now);
int x = st + (ed - st) / 3, y = st + ((ed - st) / 3) * 2;
ans[v][st] = (now);
ans[v][ed] = (bef);
for (int i = st + 1; i <= x; i++) {
ans[v][i] = (((v+2)/3)*3 + 1);
}
for (int i = x + 1; i <= y; i++) {
ans[v][i] = (((v+2)/3)*3 + 2);
}
for (int i = y + 1; i < ed; i++) {
ans[v][i] = (((v+2)/3)*3 + 3);
}
ans[((v+2)/3)*3 + 1][st] = (bef);
for (int i = x + 1; i < ed; i++) {
ans[((v+2)/3)*3 + 1][i] = (now);
}
ans[((v+2)/3)*3 + 1][ed] = (now);
solve(ans, st + 1, x, ((v+2)/3)*3 + 1, now);
ans[((v+2)/3)*3 + 2][st] = (bef);
for (int i = st + 1; i <= x; i++) {
ans[((v+2)/3)*3 + 2][i] = (bef);
}
for (int i = y; i < ed; i++) {
ans[((v+2)/3)*3 + 2][i] = (now);
}
ans[((v+2)/3)*3 + 2][ed] = (now);
solve(ans, x + 1, y, ((v+2)/3)*3 + 2, now);
ans[((v+2)/3)*3 + 3][st] = (bef);
for (int i = st + 1; i <= y; i++) {
ans[((v+2)/3)*3 + 3][i] = (bef);
}
ans[((v+2)/3)*3 + 3][ed] = (now);
solve(ans, y + 1, ed - 1, ((v+2)/3)*3 + 3, now);
}
}
vector< vector<int> > devise_strategy(int N) {
vector< vector<int> > ans;
findx(1, N, 0);
for (int i = 0; i <= X; i++) {
vector<int> temp;
for (int j = 0; j <= N; j++) temp.push_back(0);
ans.push_back(temp);
}
solve(ans, 1, N, 0, -2);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
288 KB |
Output is correct |
| 5 |
Correct |
2 ms |
288 KB |
Output is correct |
| 6 |
Correct |
1 ms |
284 KB |
Output is correct |
| 7 |
Correct |
1 ms |
288 KB |
Output is correct |
| 8 |
Correct |
2 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
284 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
284 KB |
Output is correct |
| 4 |
Correct |
12 ms |
468 KB |
Output is correct |
| 5 |
Correct |
12 ms |
864 KB |
Output is correct |
| 6 |
Correct |
13 ms |
928 KB |
Output is correct |
| 7 |
Correct |
13 ms |
924 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
212 KB |
Output is correct |
| 10 |
Correct |
2 ms |
284 KB |
Output is correct |
| 11 |
Correct |
5 ms |
568 KB |
Output is correct |
| 12 |
Correct |
12 ms |
780 KB |
Output is correct |
