Submission #146659

#	Time	Username	Problem	Language	Result	Execution time	Memory
146659		jwvg0425	Vision Program (IOI19_vision)	C++17	100 / 100	32 ms	2936 KiB

vision

#include "vision.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int h, w, k;

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

vector<int> range(int s, int e)
{
    vector<int> v;

    for (int i = s; i <= e; i++)
        v.push_back(i);

    return v;
}

// x + y = v인 셀
vector<int> allXPY(int v)
{
    vector<int> res;

    for (int x = 0; x < w; x++)
    {
        int y = v - x;
        if (y >= h || y < 0)
            continue;

        res.push_back(cell(x, y));
    }

    return res;
}

// x - y = v인 셀
vector<int> allXMY(int v)
{
    vector<int> res;

    for (int x = 0; x < w; x++)
    {
        int y = x - v;
        if (y >= h || y < 0)
            continue;

        res.push_back(cell(x, y));
    }

    return res;
}

int xpy[405];
int xmy[405];

void construct_network(int H, int W, int K) {
    h = H; w = W; k = K;

    for (int v = 0; v <= H + W - 2; v++)
        xpy[v] = add_or(allXPY(v));

    for (int v = -(H - 1); v <= W - 1; v++)
        xmy[v + 202] = add_or(allXMY(v));

    // 각각 정확히 k, k 이하
    int xpyk, xpykle;
    int xmyk, xmykle;

    vector<int> pq, pleq, mq, mleq;
    for (int v = k; v <= H + W - 2; v++)
        pq.push_back(add_and({ xpy[v], xpy[v - k] }));

    for (int v = 1; v <= H + W - 2; v++)
    {
        int r = add_or(range(xpy[max(0, v - k)], xpy[v - 1]));
        pleq.push_back(add_and({ r, xpy[v] }));
    }
    // 딱 하나 (x+y값 일치 두 개)
    pleq.push_back(add_xor(range(xpy[0], xpy[H + W - 2])));

    for (int v = -(H - 1) + k; v <= W - 1; v++)
        mq.push_back(add_and({ xmy[v + 202], xmy[v - k + 202] }));

    for (int v = -(H - 1) + 1; v <= W - 1; v++)
    {
        int r = add_or(range(xmy[max(-(H - 1), v - k) + 202], xmy[v - 1 + 202]));
        mleq.push_back(add_and({ r, xmy[v + 202] }));
    }
    mleq.push_back(add_xor(range(xmy[-(H - 1) + 202], xmy[W - 1 + 202])));

    xpyk = add_or(pq);
    xpykle = add_or(pleq);
    xmyk = add_or(mq);
    xmykle = add_or(mleq);

    int p = add_and({ xpyk, xmykle });
    int m = add_and({ xmyk, xpykle });

    add_or({ p,m });
}

• 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