제출 #817178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817178		Pikachu	Vision Program (IOI19_vision)	C++17	44 / 100	2 ms	1104 KiB

vision

#include <bits/stdc++.h>
#include "vision.h"

using namespace std;


const int maxprime = 46;
int prime[46] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199};

const int maxn = 210;
int n, m, k;
int row[maxn];
int col[maxn];
int row2[maxn];
int col2[maxn];

int getIndex(int x, int y)
{
    return x * m + y;
};

void solvemax100()
{
    for (int i = 0; i < n; i++) {
        vector<int> tmp;
        for (int j = 0; j < m; j++) {
            tmp.push_back(getIndex(i, j));
        }
        row[i] = add_or(tmp);
    }

    for (int j = 0; j < m; j++) {
        vector<int> tmp;
        for (int i = 0; i < n; i++) {
            tmp.push_back(getIndex(i, j));
        }
        col[j] = add_or(tmp);
    }

    for (int i = 1; i < n; i++) {
        vector<int> tmp;
        for (int j = 0; j + i < n; j++) {
            tmp.push_back(add_and({row[j], row[j + i]}));
        }
        row2[i] = (int)tmp.size() == 1 ? tmp.back() : add_or(tmp);
    }
    row2[0] = (n == 1) ? -1 : add_not(add_or(vector<int>(row2 + 1, row2 + n)));
    
    for (int i = 1; i < m; i++) {
        vector<int> tmp;
        for (int j = 0; j + i < m; j++) {
            tmp.push_back(add_and({col[j], col[j + i]}));
        }
        col2[i] = (int)tmp.size() == 1 ? tmp.back() : add_or(tmp);
    }
    col2[0] = (m == 1) ? -1 : add_not(add_or(vector<int>(col2 + 1, col2 + m)));

    vector<int> tmp;
    for (int i = 0; i <= min(n - 1, k); i++) {
        int j = k - i;
        if (!(0 <= j && j < m)) continue;
        if (row2[i] == -1) tmp.push_back(col2[j]);
        else if (col2[j] == -1) tmp.push_back(row2[i]); 
        else tmp.push_back(add_and({row2[i], col2[j]}));
    }

    add_or(tmp);
}

void solvemin1()
{
    vector<int> tmp;
    if (n == 1) {
        for (int j = 0; j + k < m; j++) {
            tmp.push_back(add_and({getIndex(0, j), getIndex(0, j + k)}));
        }
    }
    else {
        for (int i = 0; i + k < n; i++) {
            tmp.push_back(add_and({getIndex(i, 0), getIndex(i + k, 0)}));
        }
    }
    add_or(tmp);
}

bool check(int i, int j) { return (0 <= i && i < n && 0 <= j && j < m); }

void solve00()
{
    vector<int> tmp;
    for (int i = 0; i <= k; i++) {
        int j = k - i;
        if (!check(i, j)) continue;
        tmp.push_back(getIndex(i, j));
    }
    add_or(tmp);
}

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void solvek1()
{
    vector<int> tmp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int d = 0; d < 4; d++) {
                int x = i + dx[d];
                int y = j + dy[d];
                if (!check(x, y)) continue;
                tmp.push_back(add_and({getIndex(i, j), getIndex(x, y)}));
            }
        }
    }
    add_or(tmp);
}

void construct_network(int n, int m, int k) 
{
    ::n = n;
    ::m = m;
    ::k = k;
    if (max(n, m) <= 100) solvemax100();
    else if (min(n, m) == 1) solvemin1();
    else if (k == 1) solvek1();
    else solve00();
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 15
• Subtask 5: 12 / 12
• Subtask 6: 0 / 8
• Subtask 7: 0 / 14
• Subtask 8: 0 / 19