제출 #610096

#제출 시각아이디문제언어결과실행 시간메모리
610096jophyyjhVision Program (IOI19_vision)C++14
100 / 100
42 ms4516 KiB
/** * Wow. Idk how to express my shock when i saw that interactive problems can be like * this! So we basically have to write a program that outputs the correct 0/1 across * all images. First thought: we can't do compare each pair of rows, this takes about * 19900 (>10000) calls. * We don't have "for" or "if" statements... Hmm. I don't wanna do int addition / * subtraction using logic gates too... Well, in general we don't have much calls * available, so perhaps in a lot of calls the num of input isn't small. Nah... * * I'd like to note down my final thought. Suppose that c_1, c_2, ..., c_m are 0/1 * bits representing whether column i has a black cell. Let's put away the case of * only one 1. Let d_i := c_1 ^ c_2 ^ ... ^ c_i, so the number of 1s in (d_i) is * the horizontal dist. Similarly we can do this for the vertical direction, then * it suffices to count the num of 1s in some cells and check if it's K. * Unfortunately, the only sol i have is to do a dp which requires an additional * K(H+W) cells. Too much... (I'll submit a brute-force version in impl1) * * This think this is a problem where scoring partials is easy, but getting full is * hard. Tinjyu gave a hint during our IOI 2022 training: consider diagonals. Take * K=1 as an example. We know that if num of calls is O(HW) we definitely fail, but * if it's O(HW) we have a large const. factor to play with (since num of calls is * the bottleneck). So, take OR on each diagonal and take AND on adjacent diagonals. * Notice that if two cells' Manhattan dist. is 1, exactly 2 pairs of adjacent * diagonals have 1 in their ANDs. * * We can generalize this approach. Assume that the two cells are u, v. We draw two * diagonals through u and two diagonals through v; since in each direction there * are exactly 2 diagonals, the max of dist. between diagonals in the same direction * would be their Manhattan dist. I guess this may be inspired by the fact that cells * whose dist. to a fixed cell form the border of a rotated square. * This is so beautiful (!), though i can hardly believe that I would be able to come * up with sth like this! In some way, it's like rotating the grid by 45deg, * transforming Manhattan into Chebyschef. * * Number of calls: 5(H+W) (idk if 5 is correct, but it must be O(H+W)) * Number of reads: (idk, but not too many) * Implementation 2 (Full solution) */ #include <bits/stdc++.h> #include "vision.h" typedef std::vector<int> vec; void construct_network(int h, int w, int K) { vec d1s, d2s; for (int d = 0; d <= h + w - 2; d++) { vec diag_cells; for (int i = 0; i < h; i++) { int j = d - i; if (0 <= j && j < w) diag_cells.push_back(i * w + j); } assert(!diag_cells.empty()); d1s.push_back(add_or(diag_cells)); } for (int d = -w + 1; d <= h - 1; d++) { vec diag_cells; for (int i = 0; i < h; i++) { int j = i - d; if (0 <= j && j < w) diag_cells.push_back(i * w + j); } assert(!diag_cells.empty()); d2s.push_back(add_or(diag_cells)); } int diags = h + w - 1; // We proceed in two parts. First checking whether the pairs in d1s and d2s // have dist. <= K, then we check whether there's one = K. vec greater_check; // should be all 0 for (int i = 0; i < diags; i++) { vec neighb1, neighb2; for (int j = 0; j < diags; j++) { int dist = std::abs(i - j); if (dist > K) { neighb1.push_back(d1s[j]); neighb2.push_back(d2s[j]); } } if (!neighb1.empty()) greater_check.push_back(add_and({add_or(neighb1), d1s[i]})); if (!neighb2.empty()) greater_check.push_back(add_and({add_or(neighb2), d2s[i]})); } int part1_flag; if (!greater_check.empty()) part1_flag = add_not(add_or(greater_check)); else part1_flag = -1; vec equal_check; for (int i = 0; i < diags; i++) { vec neighb1, neighb2; if (i + K < diags) { neighb1.push_back(d1s[i + K]); neighb2.push_back(d2s[i + K]); } if (i - K >= 0) { neighb1.push_back(d1s[i - K]); neighb2.push_back(d2s[i - K]); } if (!neighb1.empty()) equal_check.push_back(add_and({add_or(neighb1), d1s[i]})); if (!neighb2.empty()) equal_check.push_back(add_and({add_or(neighb2), d2s[i]})); } assert(!equal_check.empty()); int part2_flag = add_or(equal_check); // if part1_flag is -1 this is the ans if (part1_flag != -1) add_and({part1_flag, part2_flag}); // ans }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...