Submission #422749

#	Time	Username	Problem	Language	Result	Execution time	Memory
422749		pliam	Vision Program (IOI19_vision)	C++14	100 / 100	66 ms	5344 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXH 205
#define MAXW 205

int h,w,k;
vector<int> right_d1,right_d2;//1=or, 2=ex2
vector<int> left_d1,left_d2;
vector<int> d1,d2;
vector<int> left_1,right_1,left_2,right_2;

int id(int x,int y){//x in 0..h-1, y in 0..w-1
	return x*w+y;
}

bool inbounds(int x,int y){
	return 0<=x&&x<h&&0<=y&&y<w;
}

int ex2(vector<int> v){
    return add_and({add_or(v),add_not(add_xor(v))});
}

void construct_network(int H, int W, int K) {
	h=H;
	w=W;
	k=K;
    left_d1.clear();
    left_d2.clear();
    right_d1.clear();
    right_d2.clear();
    //left diagonals
	for(int y=0;y<w;y++){
        d1.clear();
        for(int i=0;i<h;i++){
            if(inbounds(i,y-i)) d1.push_back(id(i,y-i));
        }
        int ans11=add_or(d1);
        int ans12=add_xor(d1);
        left_d1.push_back(ans11);
        left_d2.push_back(ans12);
    }
    for(int x=1;x<h;x++){
        d1.clear();
        for(int i=0;i<w;i++){
            if(inbounds(x+i,w-1-i)) d1.push_back(id(x+i,w-1-i));
        }
        int ans11=add_or(d1);
        int ans12=add_xor(d1);
        left_d1.push_back(ans11);
        left_d2.push_back(ans12);
    }
    //right diagonals
    for(int x=h-1;x>0;x--){
        d2.clear();
        for(int i=0;i<w;i++){
            if(inbounds(x+i,i)) d2.push_back(id(x+i,i));
        }
        int ans21=add_or(d2);
        int ans22=add_xor(d2);
        right_d1.push_back(ans21);
        right_d2.push_back(ans22);
    }
    for(int y=0;y<w;y++){
        d2.clear();
        for(int i=0;i<h;i++){
            if(inbounds(i,y+i)) d2.push_back(id(i,y+i));
        }
        int ans21=add_or(d2);
        int ans22=add_xor(d2);
        right_d1.push_back(ans21);
        right_d2.push_back(ans22);
    }

    left_1.clear();
    right_1.clear();
    left_2.clear();
    right_2.clear();
    for(int i=0;i<h+w-k;i++){
        vector<int> wantedl1=vector<int>(&left_d1[i],&left_d1[i+k]);
        vector<int> wantedl2=vector<int>(&left_d2[i],&left_d2[i+k]);
        left_1.push_back(add_and({add_or(wantedl1),add_not(add_xor(wantedl2))}));

        vector<int> wantedr1=vector<int>(&right_d1[i],&right_d1[i+k]);
        vector<int> wantedr2=vector<int>(&right_d2[i],&right_d2[i+k]);
        right_1.push_back(add_and({add_or(wantedr1),add_not(add_xor(wantedr2))}));
    }
    int ans1=add_and({add_or(left_1),add_or(right_1)});
    for(int i=0;i<h+w-k-1;i++){
        vector<int> wantedl1=vector<int>(&left_d1[i],&left_d1[i+k+1]);
        vector<int> wantedl2=vector<int>(&left_d2[i],&left_d2[i+k+1]);
        left_2.push_back(add_and({add_or(wantedl1),add_not(add_xor(wantedl2))}));

        vector<int> wantedr1=vector<int>(&right_d1[i],&right_d1[i+k+1]);
        vector<int> wantedr2=vector<int>(&right_d2[i],&right_d2[i+k+1]);
        right_2.push_back(add_and({add_or(wantedr1),add_not(add_xor(wantedr2))}));
    }
    int ans2=add_and({add_or(left_2),add_or(right_2)});

    add_xor({ans1,ans2});
}

• 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