Submission #581620

#	Time	Username	Problem	Language	Result	Execution time	Memory
581620		georgievskiy	Vision Program (IOI19_vision)	C++14	100 / 100	89 ms	9316 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

int has2(vector<int> a, int or_ = -1) {
    if (or_ == -1) or_ = add_or(a);
    int xor_ = add_xor(a);
    int nxor_ = add_not(xor_);
    int ans = add_and(vector<int>({nxor_, or_}));
    return ans;
}

vector<vector<int>> dr, dl;
vector<int> dl_or, dr_or;
int dl_has2_all, dr_has2_all;

void precalc(int n, int m, int k) {
    dl.resize(n + m - 1), dr.resize(n + m - 1);
    int pi = 0;
    for (int i = n - 1; i >= 0; i--, pi++) {
        for (int x = i, y = 0; x < n && y < m; x++, y++)
            dr[pi].push_back(x * m + y);
    }
    for (int j = 1; j < m; j++, pi++) {
        for (int x = 0, y = j; x < n && y < m; x++, y++)
            dr[pi].push_back(x * m + y);
    }
    pi=0;
    for (int i = n - 1; i >= 0; i--, pi++) {
        for (int x = i, y = m - 1; x < n && y >= 0; x++, y--)
            dl[pi].push_back(x * m + y);
    }
    for (int j = m - 2; j >= 0; j--, pi++) {
        for (int x = 0, y = j; x < n && y >= 0; x++, y--)
            dl[pi].push_back(x * m + y);
    }
    vector<int> dl_has2, dr_has2;

    for (auto diag : dl)
        dl_or.push_back(add_or(diag));
    for (auto diag : dr)
        dr_or.push_back(add_or(diag));

    for (int i = 0; i < n + m - 1; i++)
        dl_has2.push_back(has2(dl[i], dl_or[i]));
    for (int i = 0; i < n + m - 1; i++)
        dr_has2.push_back(has2(dr[i], dr_or[i]));

    dl_has2_all = add_or(dl_has2), dr_has2_all = add_or(dr_has2);
}

int construct_less(int n, int m, int k) {
    vector<int> dl_k, dr_k;
    for (int i = 0; i + 1 < n + m - 1; i++) {
        vector<int> t;
        for (int j = i; j < i + k && j < n + m - 1; j++) {
            t.push_back(dl_or[j]);
        }
        dl_k.push_back(has2(t));
        //cout << "dl_k[]" << i << '=' << dl_k[i] << '\n';
    }
    for (int i = 0; i + 1 < n + m - 1; i++) {
        vector<int> t;
        for (int j = i; j < i + k && j < n + m - 1; j++) {
            t.push_back(dr_or[j]);
        }
        dr_k.push_back(has2(t));
        //cout << "dr_k[]" << i << '=' << dr_k[i] << '\n';
    }
    dl_k.push_back(dl_has2_all), dr_k.push_back(dr_has2_all);

    int dl_k_all = add_or(dl_k), dr_k_all = add_or(dr_k);

    int ans = add_and(vector<int>({dl_k_all, dr_k_all}));

    return ans;
}

void construct_network(int n, int m, int k) {
    precalc(n, m, k);
    int x = construct_less(n, m, k);
    int y = construct_less(n, m, k + 1);
    int nx = add_not(x);
    int ans = add_and(vector<int>({nx, y}));
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:85:9: warning: unused variable 'ans' [-Wunused-variable]
   85 |     int ans = add_and(vector<int>({nx, y}));
      |         ^~~

• 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