Submission #1158672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158672		emptypringlescan	Vision Program (IOI19_vision)	C++20	100 / 100	33 ms	5192 KiB

vision

#include <bits/stdc++.h>
using namespace std;
#include "vision.h"
// B = H+W-1, diagonal /, diagonal2 \
// 0 , H*W-1
// H*W , H*W + B - 1 -> diagonal or
// H*W + B, H*W + 2B - 1 -> diagonal2 or 
// H*W + 2B, H*W + 3B - 1 -> and of 2 diagonals
// H*W + 3B, H*W + 4B - 1 -> and of 2 diagonals2 
// H*W + 4B, H*W + 5B - 1 -> diagonal xor
// H*W + 5B, H*W + 6B - 1 -> diagonal2 xor 
// H*W + 6B, H*W + 7B - 1 -> or of k+1 diagonals or
// H*W + 7B, H*W + 8B - 1 -> or of k+1 diagonals2 or
// H*W + 8B, H*W + 9B - 1 -> k+1 diagonals or xor k+1 diagonals xor
// H*W + 9B, H*W + 10B - 1 -> k+1 diagonals2 or xor k+1 diagonals2 xor
// H*W + 10B -> or of [H*W + 2B, H*W + 3B - 1 - K]
// H*W + 10B + 1 -> or of [H*W + 3B, H*W + 4B - 1 - K]
// H*W + 10B + 2 -> or of [H*W + 8B, H*W + 9B - 1]
// H*W + 10B + 3 -> or of [H*W + 9B, H*W + 10B - 1]
// H*W + 10B + 4 -> H*W + 10B and H*W + 10B + 3
// H*W + 10B + 5 -> H*W + 10B + 1 and H*W + 10B + 2
// H*W + 10B + 6 -> H*W + 10B + 4 or H*W + 10B + 5
void construct_network(int h, int w, int k){
	vector<int> lol;
	int b=h+w-1;
	// H*W , H*W + B - 1 -> diagonal or
	for(int i=0; i<b; i++){
		lol.clear();
		pair<int,int> cur={max(0,i-w+1),min(w-1,i)};
		while(cur.first<h&&cur.second>=0){
			lol.push_back(cur.first*w+cur.second);
			cur.first++; cur.second--;
		}
		add_or(lol);
	}
	// H*W + B, H*W + 2B - 1 -> diagonal2 or 
	for(int i=0; i<b; i++){
		lol.clear();
		pair<int,int> cur={max(0,h-i-1),max(0,i-h+1)};
		while(cur.first<h&&cur.second<w){
			lol.push_back(cur.first*w+cur.second);
			cur.first++; cur.second++;
		}
		add_or(lol);
	}
	// H*W + 2B, H*W + 3B - 1 -> and of 2 diagonals
	for(int i=0; i<b; i++){
		lol.clear();
		lol.push_back(h*w+i);
		if(i+k<b) lol.push_back(h*w+i+k);
		add_and(lol);
	}
	// H*W + 3B, H*W + 4B - 1 -> and of 2 diagonals2 
	for(int i=0; i<b; i++){
		lol.clear();
		lol.push_back(h*w+b+i);
		if(i+k<b) lol.push_back(h*w+b+i+k);
		add_and(lol);
	}
	// H*W + 4B, H*W + 5B - 1 -> diagonal xor
	for(int i=0; i<b; i++){
		lol.clear();
		pair<int,int> cur={max(0,i-w+1),min(w-1,i)};
		while(cur.first<h&&cur.second>=0){
			lol.push_back(cur.first*w+cur.second);
			cur.first++; cur.second--;
		}
		add_xor(lol);
	}
	// H*W + 5B, H*W + 6B - 1 -> diagonal2 xor 
	for(int i=0; i<b; i++){
		lol.clear();
		pair<int,int> cur={max(0,h-i-1),max(0,i-h+1)};
		while(cur.first<h&&cur.second<w){
			lol.push_back(cur.first*w+cur.second);
			cur.first++; cur.second++;
		}
		add_xor(lol);
	}
	// H*W + 6B, H*W + 7B - 1 -> or of k+1 diagonals or
	for(int i=0; i<b; i++){
		lol.clear();
		for(int j=0; j<=k; j++){
			if(i+j>=b) break;
			lol.push_back(h*w+i+j);
		}
		add_or(lol);
	}
	// H*W + 7B, H*W + 8B - 1 -> or of k+1 diagonals2 or
	for(int i=0; i<b; i++){
		lol.clear();
		for(int j=0; j<=k; j++){
			if(i+j>=b) break;
			lol.push_back(h*w+b+i+j);
		}
		add_or(lol);
	}
	// H*W + 8B, H*W + 9B - 1 -> k+1 diagonals or xor k+1 diagonals xor
	for(int i=0; i<b; i++){
		lol.clear();
		lol.push_back(h*w+6*b+i);
		for(int j=0; j<=k; j++){
			if(i+j>=b) break;
			lol.push_back(h*w+4*b+i+j);
		}
		add_xor(lol);
	}
	// H*W + 9B, H*W + 10B - 1 -> k+1 diagonals2 or xor k+1 diagonals2 xor
	for(int i=0; i<b; i++){
		lol.clear();
		lol.push_back(h*w+7*b+i);
		for(int j=0; j<=k; j++){
			if(i+j>=b) break;
			lol.push_back(h*w+5*b+i+j);
		}
		add_xor(lol);
	}
	// H*W + 10B -> or of [H*W + 2B, H*W + 3B - 1 - K]
	lol.clear();
	for(int i=h*w+2*b; i<=h*w+3*b-1-k; i++) lol.push_back(i);
	add_or(lol);
	// H*W + 10B + 1 -> or of [H*W + 3B, H*W + 4B - 1 - K]
	lol.clear();
	for(int i=h*w+3*b; i<=h*w+4*b-1-k; i++) lol.push_back(i);
	add_or(lol);
	// H*W + 10B + 2 -> or of [H*W + 8B, H*W + 9B - 1]
	lol.clear();
	for(int i=h*w+8*b; i<=h*w+9*b-1; i++) lol.push_back(i);
	add_or(lol);
	// H*W + 10B + 3 -> or of [H*W + 9B, H*W + 10B - 1]
	lol.clear();
	for(int i=h*w+9*b; i<=h*w+10*b-1; i++) lol.push_back(i);
	add_or(lol);
	// H*W + 10B + 4 -> H*W + 10B and H*W + 10B + 3
	add_and({h*w+10*b,h*w+10*b+3});
	// H*W + 10B + 5 -> H*W + 10B + 1 and H*W + 10B + 2
	add_and({h*w+10*b+1,h*w+10*b+2});
	// H*W + 10B + 6 -> H*W + 10B + 4 or H*W + 10B + 5
	add_or({h*w+10*b+4,h*w+10*b+5});
}

• 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