제출 #1247138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247138		eradax	Vision Program (IOI19_vision)	C++20	100 / 100	28 ms	4548 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

using pi = pair<int, int>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;

#define sz(c) ((int)c.size())
#define bet(l, x, h) ((l) <= (x) && (x) < (h))

#ifdef DBG
ofstream dbgs("dbg.txt");
#define dbg(expr) dbgs << "[" << __FUNCTION__ << ", " << __LINE__ << "] " << #expr << ": " << expr << endl
#else
#define dbg(...)
#endif

ostream& operator<<(ostream& o, const vi& v) {
    o << "{";
    for (auto i : v)
        o << i << ", ";
    o << "}";
    return o;
}

vi digl_or, digr_or;
int rline, lline;
int H, W, K;
int inst;

void construct_network(int _H, int _W, int _K) {
    H = _H;
    W = _W;
    K = _K;
    inst = H * W;


    auto gen_line = [](int delt, int delt2, pi p, auto func, vi& v) {
        vi line;

        dbg(p.first);
        dbg(p.second);

        for (; bet(0, p.first, H) && bet(0, p.second, W); p.first += delt, p.second += delt2)
            line.push_back(p.first * W + p.second);

        dbg(line);

        func(line);
        v.push_back(inst++); 
    };

    for (int i = H - 1; i >= 0; i--)
        gen_line(1, 1, {i, 0}, add_or, digr_or);
    for (int i = 1; i < W; i++)
        gen_line(1, 1, {0, i}, add_or, digr_or);

    add_xor(digr_or);
    rline = inst++;

    for (int i = 0; i < W; i++)
        gen_line(1, -1, {0, i}, add_or, digl_or);
    for (int i = 1; i < H; i++)
        gen_line(1, -1, {i, W-1}, add_or, digl_or);

    add_xor(digl_or);
    lline = inst++;

    auto consec = [](int k, vi& digor, int Q) {
        vi ret;
        dbg(H + W - k);
        for (int i = 0; i < H + W - k; i++) {
            vi intv;
            for (int j = 0; j < k; j++)
                intv.push_back(digor[i + j]);
            dbg(intv);
            
            add_or(intv); // P
            inst++;
            add_xor(intv); // P'
            inst++;
            add_not(inst - 1); // not P'
            inst++;
            add_or({inst - 1, Q});
            inst++;

            add_and({inst - 4, inst - 1}); // P & not P'
            ret.push_back(inst++);
        }

        return ret;
    };

    vi k_consec_r = consec(K, digr_or, rline);
    vi k_consec_l = consec(K, digl_or, lline);
    vi kp_consec_r = consec(K+1, digr_or, rline);
    vi kp_consec_l = consec(K+1, digl_or, lline);

    add_or(k_consec_l);
    inst++;
    add_or(k_consec_r);
    inst++;

    add_and({inst - 1, inst - 2});
    inst++;

    add_or(kp_consec_l);
    inst++;
    add_or(kp_consec_r);
    inst++;

    add_and({inst - 1, inst - 2});
    inst++;

    add_xor({inst - 1, inst - 4});
}

• 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