Submission #1246893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246893		eradax	Vision Program (IOI19_vision)	C++20	59 / 100	11 ms	2116 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;
vi digl_xor, digr_xor;
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);
        // dbg(func);

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

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


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

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

    
    auto consec = [](int k, vi& digor, vi& digxor) {
        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);
            inst++;
            add_xor(intv);
            inst++;
            add_not(inst - 1);
            inst++;
            add_and({inst - 1, inst - 3});
            inst++;

            intv.clear();
            for (int j = 0; j < k; j++)
                intv.push_back(digxor[i + j]);
            
            add_or(intv);
            inst++;

            add_not(inst - 1);
            inst++;

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

            add_or({inst - 1, inst - 4});
            ret.push_back(inst++);
        }

        return ret;
    };

    if (K == H + W - 2) { // Same but perhaps edgecase
        vi k_consec_r = consec(K, digr_or, digr_xor);
        vi k_consec_l = consec(K, digl_or, digl_xor);
        vi kp_consec_r = consec(K+1, digr_or, digr_xor);
        vi kp_consec_l = consec(K+1, digl_or, digl_xor);

        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});
    } else {
        vi k_consec_r = consec(K, digr_or, digr_xor);
        vi k_consec_l = consec(K, digl_or, digl_xor);
        vi kp_consec_r = consec(K+1, digr_or, digr_xor);
        vi kp_consec_l = consec(K+1, digl_or, digl_xor);

        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: 0 / 8
• Subtask 7: 0 / 14
• Subtask 8: 0 / 19