Submission #761236

#	Time	Username	Problem	Language	Result	Execution time	Memory
761236		boris_mihov	Vision Program (IOI19_vision)	C++17	100 / 100	42 ms	5808 KiB

vision

#include "vision.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200 + 10;
const int INF  = 1e9;

int n, m;
int getCellNum(int row, int col)
{
    return row * m + col;
}

int idxLeftOR[2 * MAXN];
int idxLeftXOR[2 * MAXN];
int idxRightOR[2 * MAXN];
int idxRightXOR[2 * MAXN];
std::vector <int> left[MAXN * 2];
std::vector <int> right[MAXN * 2];

int solveFor(int k)
{
    std::vector <int> leftOR, rightOR;
    for (int i = 0 ; i == 0 || i + k + 1 < n + m ; ++i)
    {
        std::vector <int> currOR, currXOR;
        for (int j = i ; j < std::min(n + m - 1, i + k + 1) ; ++j)
        {
            currOR.push_back(idxLeftOR[j]);
            currXOR.push_back(idxLeftXOR[j]);
        }

        int resOR = add_or(currOR);
        int resXOR = add_xor(currXOR);
        resXOR = add_not(resXOR);
        std::vector <int> currPair; 
        currPair.push_back(resOR); currPair.push_back(resXOR);
        resXOR = add_and(currPair);
        leftOR.push_back(resXOR);
    }

    for (int i = 0 ; i == 0 || i + k + 1 < n + m ; ++i)
    {
        std::vector <int> currOR, currXOR;
        for (int j = i ; j < std::min(n + m - 1, i + k + 1) ; ++j)
        {
            currOR.push_back(idxRightOR[j]);
            currXOR.push_back(idxRightXOR[j]);
        }

        int resOR = add_or(currOR);
        int resXOR = add_xor(currXOR);
        resXOR = add_not(resXOR);
        std::vector <int> currPair; 
        currPair.push_back(resOR); currPair.push_back(resXOR);
        resXOR = add_and(currPair);
        rightOR.push_back(resXOR);
    }

    int resLeft = add_or(leftOR);
    int resRight = add_or(rightOR);
    std::vector <int> res;
    res.push_back(resLeft);
    res.push_back(resRight);
    return add_and(res);
}

void construct_network(int H, int W, int K)
{
	n = H;
    m = W;

    for (int row = 0 ; row < n ; ++row)
    {
        for (int col = 0 ; col < m ; ++col)
        {
            right[row + col].push_back(getCellNum(row, col));
            left[row + m - 1 - col].push_back(getCellNum(row, col));
        }
    }

    for (int i = 0 ; i < n + m - 1 ; ++i)
    {
        idxLeftOR[i] = add_or(left[i]); 
        idxLeftXOR[i] = add_xor(left[i]); 
        idxRightOR[i] = add_or(right[i]); 
        idxRightXOR[i] = add_xor(right[i]); 
    }

    int first = solveFor(K);
    if (K == 1)
    {
        return;
    }

    int second = solveFor(K - 1);
    std::vector <int> ans;
    ans.push_back(first);
    ans.push_back(second);
    add_xor(ans);
}

• 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