Submission #143651

#	Time	Username	Problem	Language	Result	Execution time	Memory
143651		imeimi2000	Vision Program (IOI19_vision)	C++17	100 / 100	55 ms	5416 KiB

vision

#include <vector>
#include <tuple>
#define fs first
#define se second

using namespace std;
typedef pair<int, int> pii;

int add_not(int);
int add_and(vector<int>);
int add_or(vector<int>);
int add_xor(vector<int>);

int check_k(vector<pii> D1, vector<pii> D2, int k) {
    vector<int> S1, S2;
    for (int i = 0; i + k < D1.size(); ++i) {
        vector<int> O, X;
        for (int j = i; j <= i + k; ++j) {
            O.push_back(D1[j].fs);
            X.push_back(D1[j].se);
        }
        int Os = add_or(O);
        int Xs = add_not(add_xor(X));
        S1.push_back(add_and({ Os, Xs }));
    }
    int V1 = add_or(S1);
    for (int i = 0; i + k < D2.size(); ++i) {
        vector<int> O, X;
        for (int j = i; j <= i + k; ++j) {
            O.push_back(D2[j].fs);
            X.push_back(D2[j].se);
        }
        int Os = add_or(O);
        int Xs = add_not(add_xor(X));
        S2.push_back(add_and({ Os, Xs }));
    }
    int V2 = add_or(S2);
    return add_and({ V1, V2 });
}

void construct_network(int h, int w, int k) {
    vector<pii> D1, D2;
    for (int i = 0; i <= h + w - 2; ++i) {
        vector<int> v;
        for (int j = 0; j < w; ++j) {
            int k = i - j;
            if (k < 0 || h <= k) continue;
            v.push_back(k * w + j);
        }
        D1.emplace_back(add_or(v), add_xor(v));
    }
    for (int i = -(w - 1); i <= h - 1; ++i) {
        vector<int> v;
        for (int j = 0; j < w; ++j) {
            int k = i + j;
            if (k < 0 || h <= k) continue;
            v.push_back(k * w + j);
        }
        D2.emplace_back(add_or(v), add_xor(v));
    }
    int K0 = check_k(D1, D2, k);
    if (k == 1) return;
    int K1 = check_k(D1, D2, k - 1);
    K1 = add_not(K1);
    add_and({ K0, K1 });
}

Compilation message (stderr)

vision.cpp: In function 'int check_k(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >, int)':
vision.cpp:16:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i + k < D1.size(); ++i) {
                     ~~~~~~^~~~~~~~~~~
vision.cpp:27:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i + k < D2.size(); ++i) {
                     ~~~~~~^~~~~~~~~~~

• 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