Submission #1185660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185660		anmattroi	Vision Program (IOI19_vision)	C++17	100 / 100	51 ms	9408 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>

using namespace std;

//add_and
//add_or
//add_xor
//add_not

vector<int> operator + (vector<int> a, vector<int> b) {
    vector<int> ans(a.begin(), a.end());
    for (int i : b) ans.emplace_back(i);
    return ans;
}

struct node {int x, y, idx;
    node() {}
    node(int _x, int _y, int _idx) : x(_x), y(_y), idx(_idx) {}
};

vector<node> nodes;

vector<int> A, B;
vector<int> C, D;

int solveFirstCase(int H, int W, int K) {
    int conditionOne, conditionTwo;
    if (1) {
        vector<int> p;
        for (int i1 = 0, i2 = 0; i1 < C.size(); i1++) {
            while (i2 < C.size() && C[i2]-C[i1] <= K) ++i2;
            --i2;
            if (i1 == i2) continue;
            vector<int> o;
            for (int i = i1; i <= i2; i++) o.emplace_back(A[i]);
            p.emplace_back(add_and({add_not(add_xor(o)), add_or(o)}));
        }
        conditionTwo = add_or(p + vector<int>{add_xor(A)});
    }
    if (1) {
        vector<int> p, q;
        for (int i1 = 0, i2 = 0; i1 < D.size(); i1++) {
            while (i2 < D.size() && D[i2]-D[i1] <= K) ++i2;
            --i2;
            if (D[i2]-D[i1] != K) continue;
            vector<int> o;
            for (int i = i1; i <= i2; i++) o.emplace_back(B[i]);
            p.emplace_back(add_and({add_not(add_xor(o)), add_or(o)}));
        }
        if (K != 1) {
            for (int i1 = 0, i2 = 0; i1 < D.size(); i1++) {
                while (i2 < D.size() && D[i2]-D[i1] < K) ++i2;
                --i2;
                if (i1 == i2) continue;
                vector<int> o;
                for (int i = i1; i <= i2; i++) o.emplace_back(B[i]);
                q.emplace_back(add_and({add_not(add_xor(o)), add_or(o)}));
            }
            conditionOne = add_and(vector<int>{add_or(p)} + vector<int>{add_not(add_or(q))});
        } else conditionOne = add_or(p);
    }
    return add_and({conditionOne, conditionTwo});
}

int solveSecondCase(int H, int W, int K) {
    int conditionOne, conditionTwo;
    if (1) {
        vector<int> p;
        for (int i1 = 0, i2 = 0; i1 < D.size(); i1++) {
            while (i2 < D.size() && D[i2]-D[i1] <= K) ++i2;
            --i2;
            if (i1 == i2) continue;
            vector<int> o;
            for (int i = i1; i <= i2; i++) o.emplace_back(B[i]);
            p.emplace_back(add_and({add_not(add_xor(o)), add_or(o)}));
        }
        conditionTwo = add_or(p + vector<int>{add_xor(B)});
    }
    if (1) {
        vector<int> p, q;
         for (int i1 = 0, i2 = 0; i1 < C.size(); i1++) {
            while (i2 < C.size() && C[i2]-C[i1] <= K) ++i2;
            --i2;
            if (C[i2]-C[i1] != K) continue;
            vector<int> o;
            for (int i = i1; i <= i2; i++) o.emplace_back(A[i]);
            p.emplace_back(add_and({add_not(add_xor(o)), add_or(o)}));
        }
        if (K != 1) {
            for (int i1 = 0, i2 = 0; i1 < C.size(); i1++) {
                while (i2 < C.size() && C[i2]-C[i1] < K) ++i2;
                --i2;
                if (i1 == i2) continue;
                vector<int> o;
                for (int i = i1; i <= i2; i++) o.emplace_back(A[i]);
                q.emplace_back(add_and({add_not(add_xor(o)), add_or(o)}));
            }
            conditionOne = add_and(vector<int>{add_or(p)} + vector<int>{add_not(add_or(q))});
        } else conditionOne = add_or(p);
    }
    return add_and({conditionOne, conditionTwo});
}

void construct_network(int H, int W, int K) {
    nodes.clear();
    A.clear();
    B.clear();
    C.clear();
    D.clear();

    for (int i = 0; i < H; i++)
    for (int j = 0; j < W; j++) {
        int x = i-j, y = i+j, idx = i*W+j;
        nodes.emplace_back(x, y, idx);
    }
    sort(nodes.begin(), nodes.end(), [&](const node &a, const node &b) {
         return a.x < b.x;
         });

    for (int i2 = 0; i2 < nodes.size();) {
        int i1 = i2;
        vector<int> nho;
        while (i2 < nodes.size() && nodes[i2].x == nodes[i1].x) {
            nho.emplace_back(nodes[i2].idx);
            ++i2;
        }
        A.emplace_back(add_or(nho));
        C.emplace_back(nodes[i1].x);
    }

    sort(nodes.begin(), nodes.end(), [&](const node &a, const node &b) {
         return a.y < b.y;
         });

    for (int i2 = 0; i2 < nodes.size();) {
        int i1 = i2;
        vector<int> nho;
        while (i2 < nodes.size() && nodes[i2].y == nodes[i1].y) {
            nho.emplace_back(nodes[i2].idx);
            ++i2;
        }
        B.emplace_back(add_or(nho));
        D.emplace_back(nodes[i1].y);
    }
    add_or({solveFirstCase(H, W, K), solveSecondCase(H, W, K)});
}

• 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