Submission #146883

#	Time	Username	Problem	Language	Result	Execution time	Memory
146883		tincamatei	Vision Program (IOI19_vision)	C++14	100 / 100	21 ms	1544 KiB

vision

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

const int MAX_N = 200;

int matr[MAX_N][MAX_N];
int diagonalP[2 * MAX_N - 1];
int diagonalS[2 * MAX_N - 1];
int distKP[2 * MAX_N - 1]; // distanta exact k
int distKS[2 * MAX_N - 1];
int windowKP[2 * MAX_N - 1]; // distanta <= K
int windowKS[2 * MAX_N - 1];
int spP[2 * MAX_N - 1];
int spS[2 * MAX_N - 1];

void construct_network(int H, int W, int K) {
	// (0, 0) - (H-1, W-1) = H + W - 2

	for(int l = 0; l < H; ++l)
		for(int c = 0; c < W; ++c)
			matr[l][c] = l * W + c;

	int constFalse = add_and({matr[0][0], add_not(matr[0][0])}), constTrue = add_not(constFalse);
	for(int d = 0; d <= H + W - 2; ++d) {
		vector<int> cellsP, cellsS;
		for(int l = 0; l < H; ++l) {
			int c = d - l;
			if(0 <= c && c < W) {
				cellsP.push_back(matr[l][c]);
				cellsS.push_back(matr[H - l - 1][c]);
			}
		}

		diagonalP[d] = add_or(cellsP);
		diagonalS[d] = add_or(cellsS);
		if(d == 0) {
			spP[d] = diagonalP[d];
			spS[d] = diagonalS[d];
		} else {
			spP[d] = add_or({spP[d - 1], diagonalP[d]});
			spS[d] = add_or({spS[d - 1], diagonalS[d]});
		}

		if(d >= K) {
			distKP[d - K] = add_and({diagonalP[d], diagonalP[d - K]});
			distKS[d - K] = add_and({diagonalS[d], diagonalS[d - K]});
			if(d >= K + 1) {
				windowKP[d - K] = add_and({diagonalP[d], spP[d - K - 1]});
				windowKS[d - K] = add_and({diagonalS[d], spS[d - K - 1]});
			}
		}
	}
	
	int sumKP, sumWindowKP, sumKS, sumWindowKS;
	vector<int> cellssumKP, cellssumWindowKP, cellssumKS, cellssumWindowKS;
	for(int i = 0; i + K <= H + W - 2; ++i) {
		cellssumKP.push_back(distKP[i]);
		cellssumKS.push_back(distKS[i]);
		
		if(i >= 1) {
			cellssumWindowKP.push_back(windowKP[i]);
			cellssumWindowKS.push_back(windowKS[i]);
		}
	}
	
	if(cellssumKP.empty()) {
		sumKP = sumKS = constFalse;
	} else {
		sumKP = add_or(cellssumKP);
		sumKS = add_or(cellssumKS);
	}
	if(cellssumWindowKP.empty())
		sumWindowKP = sumWindowKS = constFalse;
	else {
		sumWindowKP = add_or(cellssumWindowKP);
		sumWindowKS = add_or(cellssumWindowKS);
	}
	
	int goodP, goodS;
	goodP = add_and({sumKP, add_not(sumWindowKS)});
	goodS = add_and({sumKS, add_not(sumWindowKP)});

	add_or({goodP, goodS});
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:24:63: warning: unused variable 'constTrue' [-Wunused-variable]
  int constFalse = add_and({matr[0][0], add_not(matr[0][0])}), constTrue = add_not(constFalse);
                                                               ^~~~~~~~~

• 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