제출 #609134

#제출 시각아이디문제언어결과실행 시간메모리
609134jophyyjhPainting Squares (IOI20_squares)C++14
100 / 100
342 ms752 KiB
/** * 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.) * * P.S. I originally stored my De Brujin Sequence in a vector<> called seq. It's * computed during paint(). The problem is (!) that NO GLOBAL VARIABLE IS * ALLOWED between the 2 functions in communication problems! So get_location() * shall compute the sequence again. * * 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; } inline vec get_seq(int n, int k) { vec seq; if (n > k) { seq = de_brujin(k); while (int(seq.size()) > n) seq.pop_back(); } else { seq = vec(n, 1); } return seq; } vec paint(int n) { // Note that the problem requires n >= k vec seq = get_seq(n, std::min(n, K)); seq.push_back(std::min(n, K)); 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); vec seq = get_seq(n, k); 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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...