Submission #654855

#	Time	Username	Problem	Language	Result	Execution time	Memory
654855		benjaminkleyn	Vision Program (IOI19_vision)	C++17	66 / 100	8 ms	1108 KiB

vision

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

void construct_network(int h, int w, int k)
{
    if (k == 1 && min(h, w) != 1)
    {
        vector<int> rw(h), cl(w);
        for (int i = 0; i < h; i++)
        {
            vector<int> idx;
            for (int j = 0; j < w; j++)
                idx.push_back(i * w + j);
            rw[i] = add_or(idx);
        }
        for (int j = 0; j < w; j++)
        {
            vector<int> idx;
            for (int i = 0; i < h; i++)
                idx.push_back(i * w + j);
            cl[j] = add_or(idx);
        }

        vector<int> a(h-1);
        for (int i = 0; i < h - 1; i++)
            a[i] = add_and({rw[i], rw[i+1]});

        vector<int> b(w-1);
        for (int j = 0; j < w - 1; j++)
            b[j] = add_and({cl[j], cl[j+1]});

        if (w == 1)
        {
            add_or(a);
            return;
        }
        if (h == 1)
        {
            add_or(b);
            return;
        }
        add_or({
            add_and({add_or(a), add_xor(cl)}),
            add_and({add_or(b), add_xor(rw)})
            });
        return;
    }
    if (max(h, w) > 30 && min(h, w) != 1)
    {
        vector<int> idx;
        for (int i = 0; i <= k; i++)
            if (i < h && k - i < w)
                idx.push_back(i * w + k - i);

        add_or(idx);
        return;
    }
    vector<int> idx1;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
        {
            vector<int> idx2;
            for (int d = 0; d < k; d++)
            {
                if (i + k - d < h && j + d < w)
                    idx2.push_back((i + k - d) * w + (j + d));
                if (i + d < h && j - k + d >= 0)
                    idx2.push_back((i + d) * w + (j - k + d));
            }
            if (idx2.size() == 0)
                continue;
            idx1.push_back(add_and({i * w + j, add_or(idx2)}));
        }
    add_or(idx1);
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 0 / 19