Submission #610096

#	Time	Username	Problem	Language	Result	Execution time	Memory
610096		jophyyjh	Vision Program (IOI19_vision)	C++14	100 / 100	42 ms	4516 KiB

vision

/**
 * 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
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19