Submission #318945

#	Time	Username	Problem	Language	Result	Execution time	Memory
318945		lohacho	Vision Program (IOI19_vision)	C++14	100 / 100	51 ms	4708 KiB

vision

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

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)204;
vector<int> line, pre, suf, resk, resK;
int kex, Kex;

void construct_network(int H, int W, int K) {
    for(int i = 0; i <= H + W - 2; ++i){
        vector<int> inp;
        for(int x = 0; x <= i; ++x){
            int y = i - x;
            if(x >= 0 && x < H && y >= 0 && y < W){
                inp.push_back(x * W + y);
            }
        }
        line.push_back(add_or(inp));
    }
    vector<int> inp;
    for(int i = 0; i < (int)line.size(); ++i){
        inp.push_back(line[i]);
        pre.push_back(add_or(inp));
    }
    inp.clear();
    for(int i = (int)line.size() - 1; i >= 0; --i){
        inp.push_back(line[i]);
        suf.push_back(add_or(inp));
    }
    reverse(suf.begin(), suf.end());
    for(int i = 0; i + K < (int)pre.size(); ++i){
        resk.push_back(add_and({pre[i], suf[i + K]}));
        if(i + K + 1 < (int)pre.size()){
            resK.push_back(add_and({pre[i], suf[i + K + 1]}));
        }
    }
    line.clear(), pre.clear(), suf.clear();
    for(int i = 0; i <= H + W - 2; ++i){
        vector<int> inp;
        for(int x = 0; x <= i; ++x){
            int y = i - x;
            if(x >= 0 && x < H && y >= 0 && y < W){
                y = W - y - 1;
                inp.push_back(x * W + y);
            }
        }
        line.push_back(add_or(inp));
    }
    inp.clear();
    for(int i = 0; i < (int)line.size(); ++i){
        inp.push_back(line[i]);
        pre.push_back(add_or(inp));
    }
    inp.clear();
    for(int i = (int)line.size() - 1; i >= 0; --i){
        inp.push_back(line[i]);
        suf.push_back(add_or(inp));
    }
    reverse(suf.begin(), suf.end());
    for(int i = 0; i + K < (int)pre.size(); ++i){
        resk.push_back(add_and({pre[i], suf[i + K]}));
        if(i + K + 1 < (int)pre.size()){
            resK.push_back(add_and({pre[i], suf[i + K + 1]}));
        }
    }
    inp.clear();
    for(auto&i:resk){
        inp.push_back(i);
    }
    kex = add_or(inp);
    inp.clear();
    for(auto&i:resK){
        inp.push_back(i);
    }
    if((int)inp.size()){
        Kex = add_or(inp);
        add_xor({kex, Kex});
    }
}

• 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