Submission #1037192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037192		shmax	Vision Program (IOI19_vision)	C++17	100 / 100	16 ms	2956 KiB

vision

#include "vision.h"

#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) (int)(x.size())

#define bit(x, i) (((x) >> i) & 1)

template<typename T>
using vec = vector<T>;

void construct_network(int H, int W, int K) {


    if (min(H, W) == 1) {
        vec<int> vals;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                for (int i1 = 0; i1 < H; i1++) {
                    for (int j1 = 0; j1 < W; j1++) {
                        if (abs(i1 - i) + abs(j1 - j) == K) {
                            vals.push_back(add_and({i * W + j, i1 * W + j1}));
                        }
                    }
                }
            }
        }
        add_or(vals);

        return;
    }



//    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);


    vec<int> rows;
    vec<int> columns;
    for (int i = 0; i < H; i++) {
        vec<int> v;
        for (int j = 0; j < W; j++) {
            v.push_back(i * W + j);
        }
        rows.push_back(add_or(v));
    }
    for (int i = 0; i < W; i++) {
        vec<int> v;
        for (int j = 0; j < H; j++) {
            v.push_back(j * W + i);
        }
        columns.push_back(add_or(v));
    }


    int TRUE = add_or(rows);

    int B = 9;
    vec<int> dx(B, add_not(TRUE));
    for (int i = 0; i < B; i++) {
        vec<int> res;
        for (int j = 0; j < H; j++) {
            vec<int> t;
            for (int k = 0; k < j; k++) {
                if (bit(j - k, i)) {
                    t.push_back(rows[k]);
                }
            }
            if (t.empty()) continue;
            int f1 = add_or(t);
            res.push_back(add_and({rows[j], f1}));
        }
        if (res.empty()) continue;
        dx[i] = add_or(res);
    }
    vec<int> dy(B,  add_not(TRUE));
    for (int i = 0; i < B; i++) {
        vec<int> res;
        for (int j = 0; j < W; j++) {
            vec<int> t;
            for (int k = 0; k < j; k++) {
                if (bit(j - k, i)) {
                    t.push_back(columns[k]);
                }
            }
            if (t.empty()) continue;

            int f1 = add_or(t);
            res.push_back(add_and({columns[j], f1}));
        }
        if (res.empty()) continue;

        dy[i] = add_or(res);
    }

    vec<int> SUM(B, 0);
    int L = -1;
    for (int i = 0; i < B; i++) {
        vec<int> to_make = {dx[i], dy[i]};
        if (L != -1)
            to_make.push_back(L);
        SUM[i] = add_xor(to_make);
        vec<int> LS;
        for (int j = 0; j < len(to_make); j++) {
            for (int t = 0; t < j; t++) {
                LS.push_back(add_and({to_make[t], to_make[j]}));
            }
        }
        L = add_or(LS);
    }

    for (int i = 0; i < B; i++) {
        if (!bit(K, i)) {
            SUM[i] = add_not(SUM[i]);
        }
    }
    add_and(SUM);
}

• 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