Submission #775994

#	Time	Username	Problem	Language	Result	Execution time	Memory
775994		_martynas	Vision Program (IOI19_vision)	C++14	100 / 100	63 ms	7432 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>

using namespace std;

void visualize(int H, int W, vector<int> A) {
    vector<vector<char>> B(H, vector<char>(W, '.'));
    for(int x : A) B[x/W][x%W] = '#';
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cerr << B[i][j];
        }
        cerr << "\n";
    }
}

void construct_network(int H, int W, int K) {
    /* sample interaction
	std::vector<int> Ns;
	Ns = {0, 1};
	int a = add_and(Ns);
	Ns = {0, a};
	int b = add_or(Ns);
	Ns = {0, 1, b};
	int c = add_xor(Ns);
	add_not(c);
	*/
    vector<vector<int>> diag1, diag2;
    diag1 = diag2 = vector<vector<int>>(H+W-1);
    /*  diag1 (down right)  diag2 (down left)
        ---------           ---------
        |c|d|e|f|           |f|e|d|c|
        ---------           ---------
        |b|c|d|e|           |e|d|c|b|
        ---------           ---------
        |a|b|c|d|           |d|c|b|a|
        ---------           ---------
    */
    // diag1
    for(int i = 0; i < H; i++) {
        for(int x = H-i-1, y = 0; x < H && y < W; x++, y++) {
            diag1[i].push_back(x*W+y);
        }
    }
    for(int i = H; i < H+W-1; i++) {
        for(int x = 0, y = i-H+1; x < H && y < W; x++, y++) {
            diag1[i].push_back(x*W+y);
        }
    }
//    for(int i = 0; i < H+W-1; i++) {
//        cerr << i << ":\n";
//        visualize(H, W, diag1[i]);
//    }
    // diag2
    for(int i = 0; i < H; i++) {
        for(int x = H-i-1, y = W-1; x < H && y >= 0; x++, y--) {
            diag2[i].push_back(x*W+y);
        }
    }
    for(int i = H; i < H+W-1; i++) {
        for(int x = 0, y = W-(i-H)-2; x < H && y >= 0; x++, y--) {
            diag2[i].push_back(x*W+y);
        }
    }
//    for(int i = 0; i < H+W-1; i++) {
//        cerr << i << ":\n";
//        visualize(H, W, diag2[i]);
//    }
    /// Returns an index to the answer
    auto dist_less_than_K = [&]() {
        vector<int> diag1_or(H+W-1), diag2_or(H+W-1); // indices not values
        vector<int> diag1_xor(H+W-1), diag2_xor(H+W-1); // indices not values
        for(int i = 0; i < H+W-1; i++) {
            vector<int> query;
            for(int x : diag1[i]) query.push_back(x);
            diag1_or[i] = add_or(query);
            diag1_xor[i] = add_xor(query);
            query.clear();
            for(int x : diag2[i]) query.push_back(x);
            diag2_or[i] = add_or(query);
            diag2_xor[i] = add_xor(query);
        }
        vector<int> diag1_range_ok, diag2_range_ok; // indices not values
        for(int i = 0; i+K-1 < H+W-1; i++) {
            vector<int> query;
            for(int j = i; j < i+K; j++) query.push_back(diag1_or[j]);
            int range_or = add_or(query);
            query.clear();
            for(int j = i; j < i+K; j++) query.push_back(diag1_xor[j]);
            int range_xor = add_xor(query);
            diag1_range_ok.push_back(add_and(vector<int>{range_or, add_not(range_xor)}));
        }
        for(int i = 0; i+K-1 < H+W-1; i++) {
            vector<int> query;
            for(int j = i; j < i+K; j++) query.push_back(diag2_or[j]);
            int range_or = add_or(query);
            query.clear();
            for(int j = i; j < i+K; j++) query.push_back(diag2_xor[j]);
            int range_xor = add_xor(query);
            diag2_range_ok.push_back(add_and(vector<int>{range_or, add_not(range_xor)}));
        }
        int ok = add_and(vector<int>{add_or(diag1_range_ok), add_or(diag2_range_ok)});
        return ok;
    };
    int ok1 = dist_less_than_K();
    K++;
    int ok2 = dist_less_than_K();
    add_and(vector<int>{add_not(ok1), ok2});
}

• 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