Submission #573924

#	Time	Username	Problem	Language	Result	Execution time	Memory
573924		Stickfish	Vision Program (IOI19_vision)	C++17	100 / 100	58 ms	5784 KiB

vision

#include "vision.h"
#include <functional>
#include <iostream>
using namespace std;

int memsz;

struct cords {
    bool rvs;
    int h;
    int w;

    int get_num(int i, int j) const {
        if (rvs)
            j = w - j - 1;
        return i * w + j;
    }
};

int get_downright(int h, int w, int k, cords cr) {
    vector<vector<int>> diags(w + h - 1);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            diags[i + j].push_back(cr.get_num(i, j));
        }
    }
    vector<int> diag_nums;
    for (int i = 0; i < h + w - 1; ++i) {
        add_xor(diags[i]);
        diag_nums.push_back(memsz);
        ++memsz;
    }
    vector<int> diag_pairs;
    for (int i = 0; i + k < h + w - 1; ++i) {
        add_and({diag_nums[i], diag_nums[i + k]});
        diag_pairs.push_back(memsz);
        ++memsz;
    }
    add_or(diag_pairs);
    int diag_check = memsz;
    ++memsz;
    vector<vector<bool>> used(h, vector<bool>(w, false));
    vector<vector<int>> end_mem(h, vector<int>(w, -1));
    vector<int> direction_check;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (!used[i][j]) {
                vector<int> start;
                vector<int> end;
                if (i && end_mem[i - 1][j] != -1)
                    end.push_back(end_mem[i - 1][j]);
                for (int j0 = j; j0 < w; j0 += 3 * k) {
                    for (int j1 = j0; j1 < j0 + k && j1 < w; ++j1) {
                        start.push_back(cr.get_num(i, j1));
                        used[i][j1] = true;
                        if (i == 0 || end_mem[i - 1][j] == -1) {
                            for (int i1 = i; i1 < h && i1 <= i + k; ++i1) {
                                if (j1 + k - (i1 - i) < w)
                                    end.push_back(cr.get_num(i1, j1 + k - (i1 - i)));
                            }
                        } else {
                            if (j1 + k < w)
                                end.push_back(cr.get_num(i - 1, j1 + k));
                            if (i + k < h)
                                end.push_back(cr.get_num(i + k, j1));
                            int t = (j0 + k - j1) - 1;
                            if (i + t < h) {
                                end.push_back(cr.get_num(i + t, j1));
                                if (j1 + k < w)
                                    end.push_back(cr.get_num(i + t, j1 + k));
                            }
                        }
                    }
                }
                if (start.empty() || end.empty())
                    continue;
                //for (auto x : start)
                    //cout << x << ' ';
                //cout << "| ";
                //for (auto x : end)
                    //cout << x << ' ';
                //cout << endl;
                add_xor(start);
                ++memsz;
                add_xor(end);
                end_mem[i][j] = memsz;
                ++memsz;
                add_and({memsz - 2, memsz - 1});
                direction_check.push_back(memsz);
                ++memsz;
            }
        }
    }
    add_or(direction_check);
    ++memsz;
    add_and({memsz - 1, diag_check});
    ++memsz;
    return memsz - 1;
}


void construct_network(int h, int w, int k) {
    int cnt = h * w;
    memsz = h * w;
    cords c;
    c.rvs = 0;
    c.h = h;
    c.w = w;
    int ans0 = get_downright(h, w, k, c);
    c.rvs = 1;
    int ans1 = get_downright(h, w, k, c);
    if (ans0 == -1)
        return;
    if (ans1 == -1) {
        add_and({ans0});
        return;
    }
    add_or({ans0, ans1});
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:103:9: warning: unused variable 'cnt' [-Wunused-variable]
  103 |     int cnt = h * w;
      |         ^~~

• 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