| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 609101 | jophyyjh | Painting Squares (IOI20_squares) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* I'm a bit disappointed. Since only k <= 10 can AC, i think the only solution would
* be to use De Brujin Sequence. k = 10 is already the minimum since it's the
* smallest positive int satisfying 2^k + k - 1 >= n. (I was looking for sth original
* when I started this problem.)
*
* K: log_2(n) (as long as 2^k + k - 1 >= n)
* Implementation 1
*/
#include <bits/stdc++.h>
#include "squares.h"
typedef std::vector<int> vec;
const int K = 10;
std::vector<vec> graph;
vec path;
void find_path(int k) {
while (!graph[k].empty()) {
int j = graph[k][graph[k].size() - 1];
graph[k].pop_back();
find_path(j);
}
path.push_back(k);
}
vec de_brujin(int k) {
path.clear();
int n = 1 << (k - 1);
graph.assign(n, vec());
for (int i = 0; i < n; i++) {
int j = (i << 1) & (n - 1);
graph[i].push_back(j);
graph[i].push_back(j | 1);
}
find_path(0);
std::reverse(path.begin(), path.end());
vec seq;
for (int b = 0, first = path[0]; b < k - 1; first >>= 1, b++)
seq.push_back(first & 1);
std::reverse(seq.begin(), seq.end());
for (int i = 1; i < int(path.size()); i++)
seq.push_back(path[i] & 1);
return seq;
}
vec paint(int n) {
vec seq;
if (n >= K) {
seq = de_brujin(K);
while (int(seq.size()) > n)
seq.pop_back();
seq.push_back(K);
} else { // the problem requires K > n
seq = vec(n, 1);
seq.push_back(n); // take k = n.
}
return seq;
}
int find_location(int n, vec c) {
int k = c.size(), out_of_bound = 0;
for (int i = k - 1; i >= 0 && c[i] == -1; i--)
out_of_bound++;
if (out_of_bound > 0)
return n - (k - out_of_bound);
for (int start = 0; start + k - 1 < n; start++) {
bool equal = true;
for (int i = 0; i < k && equal; i++)
equal &= (seq[start + i] == c[i]);
if (equal)
return start;
}
std::cerr << "error" << std::endl;
std::abort();
}