제출 #143855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143855		RezwanArefin01	Vision Program (IOI19_vision)	C++17	100 / 100	16 ms	1656 KiB

vision

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

using namespace std; 

void construct_network(int H, int W, int K) {
    for(int i = 0; i < H; ++i) {
        vector<int> v; 
        for(int j = 0; j < W; ++j) {
            v.push_back(i * W + j);
        }
        if(i) v.push_back(H * W + i - 1); 
        add_xor(v);
    }

    for(int j = 0; j < W; ++j) {
        vector<int> v; 
        for(int i = 0; i < H; ++i) {
            v.push_back(i * W + j); 
        }
        if(j) v.push_back(H * W + H + j - 1); 
        add_xor(v); 
    }

    int B = ceil(log2(H + W));

    add_or({ H * W + H - 1 });
    add_or({ H * W }); 

    for(int i = 2; i < 2 * B; ++i) 
        add_or({ H * W + H - 1 });


    int s = H * W + H + W; 
    for(int k = 1; k < H + W; ++k, s += 2 * B) {
        int c = H * W + k;

        add_or({ c }); 
        add_xor({ s + 1, c });
        
        for(int i = 1; i < B; ++i) {
            add_and({ s + 2 * i - 1, s + 2 * B + 2 * (i - 1) });
            add_xor({ s + 2 * i + 1, s + 2 * B + 2 * i }); 
        }
    }

    for(int i = 0; i < B; ++i) {
        if(K >> i & 1) {
            add_or({ s + 2 * i + 1 }); 
        } else {
            add_not({ s + 2 * i + 1 });
        }
    }

    vector<int> v(B);
    iota(v.begin(), v.end(), s + 2 * B);
    add_and(v);
}

• 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