Submission #1063462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063462		Zicrus	Vision Program (IOI19_vision)	C++17	100 / 100	13 ms	2008 KiB

vision

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

typedef long long ll;

int h, w, k;

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

void construct_network(int H, int W, int K) {
    // Generate prime powers
    vector<ll> p = {2, 3, 5, 7, 11};
    for (int i = p.back(); i < 200; i++) {
        bool prime = true;
        for (auto &e : p) {
            if (i % e == 0) prime = false;
        }
        if (prime) p.push_back(i);
    }
    vector<ll> pp;
    for (auto &e : p) {
        ll val = e;
        while (val < 200) {
            pp.push_back(val);
            val *= e;
        }
    }
    sort(pp.begin(), pp.end());

    // Rows and columns
    h = H; w = W; k = K;
    vector<int> col(w), row(h);
    for (int i = 0; i < w; i++) {
        vector<int> c(h);
        for (int j = 0; j < h; j++) c[j] = coord(i, j);
        col[i] = add_or(c);
    }
    for (int j = 0; j < h; j++) {
        vector<int> r(w);
        for (int i = 0; i < w; i++) r[i] = coord(i, j);
        row[j] = add_or(r);
    }

    // Prime power distances
    vector<int> wPPNot(w), hPPNot(h);
    vector<int> wPP(w), hPP(h);
    for (auto &e : pp) {
        if (e >= w) break;
        vector<int> pos;
        for (int i = 0; i < min(e, w-e); i++) {
            vector<int> stones;
            for (int j = i; j < w; j += e) {
                stones.push_back(col[j]);
            }
            pos.push_back(add_xor(stones));
        }
        if (e > w/2) {
            vector<int> tmp;
            for (int i = w-e; i < e; i++) {
                tmp.push_back(col[i]);
            }
            pos.push_back(add_or(tmp));
        }
        wPPNot[e] = add_or(pos);
        wPP[e] = add_not(wPPNot[e]);
    }
    for (auto &e : pp) {
        if (e >= h) break;
        vector<int> pos;
        for (int i = 0; i < min(e, h-e); i++) {
            vector<int> stones;
            for (int j = i; j < h; j += e) {
                stones.push_back(row[j]);
            }
            pos.push_back(add_xor(stones));
        }
        if (e > h/2) {
            vector<int> tmp;
            for (int i = h-e; i < e; i++) {
                tmp.push_back(row[i]);
            }
            pos.push_back(add_or(tmp));
        }
        hPPNot[e] = add_or(pos);
        hPP[e] = add_not(hPPNot[e]);
    }

    vector<int> res;
    int zeroW = add_xor(col);
    int zeroH = add_xor(row);
    int zeroWNot = add_not(zeroW);
    int zeroHNot = add_not(zeroH);
    for (int i = 0; i < min(w, k+1); i++) {
        if (k-i >= h) continue;
        vector<int> tst;
        if (i == 0) {
            tst.push_back(zeroW);
        }
        else {
            if (i == 1) tst.push_back(zeroWNot);
            for (auto &e : p) {
                if (e >= w) break;
                ll val = e;
                while (i % val == 0) val *= e;
                if (val < w) tst.push_back(wPPNot[val]);
                if (val/e > 1) tst.push_back(wPP[val/e]);
            }
        }
        ll vert = k - i;
        if (vert == 0) {
            tst.push_back(zeroH);
        }
        else {
            if (vert == 1) tst.push_back(zeroHNot);
            for (auto &e : p) {
                if (e >= h) break;
                ll val = e;
                while (vert % val == 0) val *= e;
                if (val < h) tst.push_back(hPPNot[val]);
                if (val/e > 1) tst.push_back(hPP[val/e]);
            }
        }
        res.push_back(add_and(tst));
    }

    add_or(res);
}

• 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