Submission #573152

#	Time	Username	Problem	Language	Result	Execution time	Memory
573152		Lawliet	Vision Program (IOI19_vision)	C++17	100 / 100	40 ms	4488 KiB

vision

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

using namespace std;

int h, w, k;

int idCell(int i, int j) { return i*w + j; }

int checkGreater(vector<int> ids, int t)
{
	vector<int> results;

	for(int i = 0 ; i + t < (int)ids.size() ; i++)
	{
		vector<int> query;

		for(int j = i + t ; j < (int)ids.size() ; j++)
			query.push_back( ids[j] );

		int suffixOr = add_or(query);
		results.push_back( add_and({ids[i], suffixOr}) );
	}

	return add_or(results);
}

void construct_network(int H, int W, int K) 
{
	h = H; w = W; k = K;

	if( k == h + w - 2 )
	{
		int a = add_and({idCell(0, 0), idCell(H - 1, W - 1)});
		int b = add_and({idCell(0, W - 1), idCell(H - 1, 0)});

		add_or({a, b});
		return;
	}

	vector<int> mainDiag, secDiag;

	for(int sum = 0 ; sum <= h + w - 2 ; sum++)
	{
		vector<int> query;

		for(int i = 0, j = sum ; i < h ; i++, j--)
			if( 0 <= j && j < w ) query.push_back( idCell(i, j) );

		mainDiag.push_back( add_or(query) );
	}	

	for(int diff = -w + 1 ; diff < h ; diff++)
	{
		vector<int> query;

		for(int i = 0, j = -diff ; i < h ; i++, j++)
			if( 0 <= j && j < w ) query.push_back( idCell(i, j) );

		secDiag.push_back( add_or(query) );
	}

	int secK = checkGreater(secDiag, k), secNxt = checkGreater(secDiag, k + 1);
	int mainK = checkGreater(mainDiag, k), mainNxt = checkGreater(mainDiag, k + 1);

	// secK or mainK must be one
	// secNxt and mainNxt must be zero

	int orK = add_or({secK, mainK});
	int orNxt = add_or({mainNxt, secNxt});

	add_xor({orK, orNxt});
}

• 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