| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1362876 | erering | 죄수들의 도전 (IOI22_prison) | C++20 | 0 ms | 0 KiB |
vector<vector<int>> devise_strategy(int N) {
vector<int> base;
int prod = 1;
while (prod < N) {
base.push_back(3);
prod *= 3;
}
int L = (int)base.size();
int x = 3 * L;
vector<vector<int>> s(x + 1, vector<int>(N + 1, 0));
auto digit = [&](int value, int pos) {
int v = value - 1;
int div = 1;
for (int k = pos + 1; k < L; ++k) div *= base[k];
return (v / div) % base[pos];
};
auto id = [&](int pos, int d) {
return 1 + pos * 3 + d;
};
s[0][0] = 0;
for (int j = 1; j <= N; ++j) {
s[0][j] = id(0, digit(j, 0));
}
for (int pos = 0; pos < L; ++pos) {
for (int stored = 0; stored < 3; ++stored) {
int state = id(pos, stored);
bool stored_from_a = (pos % 2 == 0);
s[state][0] = stored_from_a ? 1 : 0;
for (int j = 1; j <= N; ++j) {
int seen = digit(j, pos);
if (stored_from_a) {
if (stored < seen) {
s[state][j] = -1;
} else if (stored > seen) {
s[state][j] = -2;
} else if (pos + 1 < L) {
s[state][j] = id(pos + 1, digit(j, pos + 1));
} else {
s[state][j] = -1;
}
} else {
if (seen < stored) {
s[state][j] = -1;
} else if (seen > stored) {
s[state][j] = -2;
} else if (pos + 1 < L) {
s[state][j] = id(pos + 1, digit(j, pos + 1));
} else {
s[state][j] = -1;
}
}
}
}
}
return s;
}