Submission #602822

#	Time	Username	Problem	Language	Result	Execution time	Memory
602822		Johann	Vision Program (IOI19_vision)	C++14	100 / 100	49 ms	5960 KiB

vision

#include "vision.h"

using namespace std;

typedef vector<int> vi;
#define sz(x) (int)(x).size()

int h, w, k;

struct diag {
    int D;
    vi P;
    int OR;
    int TWO;
};

int calc_pos(int x, int y) {
    return y * w + x;
}

int check_auf_zwei_Punkte(vi &q, int pos_or) {
    return add_and({pos_or, add_not(add_xor(q))});
}

int check_diag(vector<diag> &D, int i, int K) {
    vi qor;
    for (int j = 0; j < K; ++j) {
        qor.push_back(D[i + j].OR);
    }
    return add_and({add_or(qor), add_not(add_xor(qor))});
}

void construct_network(int H, int W, int K) {
    h = H;
    w = W;
    k = K;
    // Rechte Diagonalen (x - y = konst)
    vector<diag> R;
    for (int d = -H + 1; d < W; ++d) {
        R.push_back(diag());
        R.back().D = d;
        for (int x = 0; x < W; ++x) {
            int y = x - d;
            if (0 <= y && y < H) {
                R.back().P.push_back(calc_pos(x, y));
            }
        }
        R.back().OR = add_or(R.back().P);
        R.back().TWO = check_auf_zwei_Punkte(R.back().P, R.back().OR);
    }
    // Linke Diagonale (x + y = konst)
    vector<diag> L;
    for (int d = 0; d <= H + W - 2; ++d) {
        L.push_back(diag());
        L.back().D = d;
        for (int x = 0; x < W; ++x) {
            int y = d - x;
            if (0 <= y && y < H) {
                L.back().P.push_back(calc_pos(x, y));
            }
        }
        L.back().OR = add_or(L.back().P);
        L.back().TWO = check_auf_zwei_Punkte(L.back().P, L.back().OR);
    }
    // Blöcke mit Größe K enthält zwei dinger...
    vi RK, LK;
    for (int i = 0; i <= sz(R) - K; ++i) {
        RK.push_back(check_diag(R, i, K));
        LK.push_back(check_diag(L, i, K));
    }
    for (int i = 0; i < sz(R); ++i) {
        RK.push_back(R[i].TWO);
        LK.push_back(L[i].TWO);
    }
    int tRK = add_or(RK);
    int tLK = add_or(LK);
    int kb = add_and({tRK, tLK});
    int nkb = add_not(kb);
    // Blöcke mit K+1 enthält zwei dinger
    vi RK1, LK1;
    for (int i = 0; i <= sz(R) - K - 1; ++i) {
        RK1.push_back(check_diag(R, i, K + 1));
        LK1.push_back(check_diag(L, i, K + 1));
    }
    for (int i = 0; i < sz(R); ++i) {
        RK1.push_back(R[i].TWO);
        LK1.push_back(L[i].TWO);
    }
    int tRK1 = add_or(RK1);
    int tLK1 = add_or(LK1);
    int kb1 = add_and({tRK1, tLK1});

    int ans = add_and({kb1, nkb});
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:93:9: warning: unused variable 'ans' [-Wunused-variable]
   93 |     int ans = add_and({kb1, nkb});
      |         ^~~

• 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