Submission #615982

#	Time	Username	Problem	Language	Result	Execution time	Memory
615982		amunduzbaev	Vision Program (IOI19_vision)	C++17	100 / 100	45 ms	5204 KiB

vision

#include "bits/stdc++.h"
using namespace std;
#include "vision.h"

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
#define sow cout<<"here"<<endl;

void construct_network(int n, int m, int k) {
	vector<vector<int>> a(n + m, vector<int>(n + m, -1));
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			a[i + j][i - j + m] = i * m + j;
		}
	}
	
	n += m;
	int r1 = -1, r2 = -1;
	{
		vector<int> idr(n, -1), idc(n, -1), xc(n, -1), T;
		
		for(int i=0;i<n;i++){
			vector<int> t;
			for(int j=0;j<n;j++){
				if(~a[i][j]) t.push_back(a[i][j]);
			}
			
			if(!t.empty()) idr[i] = add_or(t);
			t.clear();
			for(int j=0;j<n;j++){
				if(~a[j][i]) t.push_back(a[j][i]);
			}
			
			if(!t.empty()) idc[i] = add_or(t), xc[i] = add_xor(t);
		}
		vector<int> tmp(n, -1);
		for(int i=0;i<n;i++){
			if(i >= k && ~idr[i] && ~idr[i - k]){
				tmp[i] = add_and({idr[i], idr[i-k]});
				T.push_back(tmp[i]);
			}
		}
		int v = -1;
		if(!T.empty()) v = add_or(T);
		T.clear();
		for(int i=0;i<n;i++){
			vector<int> t;
			for(int j=max(0, i-k);j<i;j++){
				if(~idc[j]) t.push_back(idc[j]);
			}
			
			int X = -1, Y = -1;
			if(!t.empty() && ~idc[i]){
				int j = add_or(t);
				X = add_and({j, idc[i]});
			}
			if(~idc[i] && ~xc[i]){
				Y = add_and({idc[i], add_not(xc[i])});
			}
			
			if(~X) T.push_back(X);
			if(~Y) T.push_back(Y);
		}
		
		int v2 = -1;
		if(!T.empty()) v2 = add_or(T);
		if(~v && ~v2) r1 = add_and({v, v2});
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			swap(a[i][j], a[j][i]);
		}
	}
	
	{
		vector<int> idr(n, -1), idc(n, -1), xc(n, -1), T;
		
		for(int i=0;i<n;i++){
			vector<int> t;
			for(int j=0;j<n;j++){
				if(~a[i][j]) t.push_back(a[i][j]);
			}
			
			if(!t.empty()) idr[i] = add_or(t);
			t.clear();
			for(int j=0;j<n;j++){
				if(~a[j][i]) t.push_back(a[j][i]);
			}
			
			if(!t.empty()) idc[i] = add_or(t), xc[i] = add_xor(t);
		}
		
		vector<int> tmp(n, -1);
		for(int i=0;i<n;i++){
			if(i >= k && ~idr[i] && ~idr[i - k]){
				tmp[i] = add_and({idr[i], idr[i-k]});
				T.push_back(tmp[i]);
			}
		}
		int v = -1;
		if(!T.empty()) v = add_or(T);
		T.clear();
		for(int i=0;i<n;i++){
			vector<int> t;
			for(int j=max(0, i-k);j<i;j++){
				if(~idc[j]) t.push_back(idc[j]);
			}
			
			int X = -1, Y = -1;
			if(!t.empty() && ~idc[i]){
				int j = add_or(t);
				X = add_and({j, idc[i]});
			}
			if(~idc[i] && ~xc[i]){
				Y = add_and({idc[i], add_not(xc[i])});
			}
			
			if(~X) T.push_back(X);
			if(~Y) T.push_back(Y);
		}
		
		int v2 = -1;
		if(!T.empty()) v2 = add_or(T);
		if(~v && ~v2) r2 = add_and({v, v2});
	}
	
	if(~r1 && ~r2){
		add_or({r1, r2});
	} else if(~r1){
		add_or({r1});
	} else if(~r2){
		add_or({r2});
	} else {
		if(k < m){
			add_and({0, k});
		} else {
			add_and({0, (k - m + 1) * m + m - 1});
		}
	}
}

• 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