Submission #241287

#	Time	Username	Problem	Language	Result	Execution time	Memory
241287		Berted	Vision Program (IOI19_vision)	C++14	100 / 100	16 ms	1408 KiB

vision

#include "vision.h"
#include <vector>
#include <iostream>

using namespace std;

vector<int> temp;
int hp[501], vp[501];
int w;

/* Idea : We check based on diagonals, since there are two diagonals, the one
that is valid is the pair that are the furthest apart. Therefore, we should check
if there is a pair of diags such that distance = K and the opposite diag must have distance <= K.*/

void construct_network(int H, int W, int K)
{
	//Diagonal 1 [HW, HW + H + W - 1)
    for (int i = 0; i < H + W - 1; i++) 
    {
    	int y = 0, x = i;
    	if (x > W - 1) {x = W - 1; y = i - W + 1;}
    	while (x >= 0 && y >= 0 && y < H && x < W)
    	{
    		temp.push_back(y * W + x);
    		y++; x--;
    	}
    	w = add_or(temp);
    	temp.clear();
    }

    //Diagonal 2 [HW + H + W - 1, HW + 2H + 2W - 2)
    for (int i = 0; i < H + W - 1; i++) 
    {
    	int y = 0, x = W - 1 - i;
    	if (x < 0) {x = 0; y = i - W + 1;}
    	while (x >= 0 && y >= 0 && y < H && x < W)
    	{
    		temp.push_back(y * W + x);
    		y++; x++;
    	}
    	w = add_or(temp);
    	temp.clear();
    }

    // Prefix Diag 1 [HW + 2H + 2W - 2, HW + 3H + 3W - 3)
    temp.push_back(H * W);
    w = add_or(temp);
    temp.clear();
    for (int i = H * W + 1; i < H * W + W + H - 1; i++)
    {
    	temp.push_back(w); temp.push_back(i);
    	w = add_or(temp);
    	temp.clear();
    }

    // Prefix Diag 2 [HW + 3H + 3W - 3, HW + 4H + 4W - 4)
    temp.push_back(H * W + W + H - 1);
    w = add_or(temp);
    temp.clear();
    for (int i = H * W + W + H; i < H * W + 2 * (W + H - 1); i++)
    {
    	temp.push_back(w); temp.push_back(i);
    	w = add_or(temp);
    	temp.clear();
    }

    // Check Diag 1 [HW + 4H + 4W - 4, HW + 5H + 5W - 5 - K)
    for (int i = K; i < H + W - 1; i++)
    {
    	temp.push_back(H * W + i);
    	temp.push_back(H * W + i - K);
    	w = add_and(temp);
    	temp.clear();
    }

    // Check Diag 2 [HW + 5H + 5W - 5 - K, HW + 6H + 6W - 6 - 2K)
    for (int i = K; i < H + W - 1; i++)
    {
    	temp.push_back(H * W + H + W - 1 + i);
    	temp.push_back(H * W + H + W - 1 + i - K);
    	w = add_and(temp);
    	temp.clear();
    }

    if (K < H + W - 2)
    {
    	// Check SDiag 1 [HW + 6H + 6W - 6 - 2K, HW + 7H + 7W - 8 - 3K)
	    for (int i = K + 1; i < H + W - 1; i++)
	    {
	    	temp.push_back(H * W + i);
	    	temp.push_back(H * W + 2 * (H + W - 1) + i - K - 1);
	    	w = add_and(temp);
	    	temp.clear();
	    }

	    // Check SDiag 2 [HW + 7H + 7W - 8 - 3K, HW + 8H + 8W - 10 - 4K)
	    for (int i = K + 1; i < H + W - 1; i++)
	    {
	    	temp.push_back(H * W + H + W - 1 + i);
	    	temp.push_back(H * W + 3 * (H + W - 1) + i - K - 1);
	    	w = add_and(temp);
	    	temp.clear();
	    }
    }
    
    // OR CD1 [HW + 8H + 8W - 10 - 4K]
    for (int i = H * W + 4 * (H + W - 1); i < H * W + 5 * (H + W - 1) - K; i++) temp.push_back(i);
    w = add_or(temp);
    temp.clear();

    // OR CD2 [HW + 8H + 8W - 9 - 4K]
    for (int i = H * W + 5 * (H + W - 1) - K; i < H * W + 6 * (H + W - 1) - 2 * K; i++) temp.push_back(i);
    w = add_or(temp);
    temp.clear();

    if (K < H + W - 2)
    {
    	// OR SCD1 [HW + 8H + 8W - 8 - 4K]
	    for (int i = H * W + 6 * (H + W - 1) - 2 * K; i < H * W + 7 * (H + W - 1) - 3 * K - 1; i++) temp.push_back(i);
	    w = add_or(temp);
	    temp.clear();

	    // OR SCD2 [HW + 8H + 8W - 7 - 4K]
	    for (int i = H * W + 7 * (H + W - 1) - 3 * K - 1; i < H * W + 8 * (H + W - 1) - 4 * K - 2; i++) temp.push_back(i);
	    w = add_or(temp);
	    temp.clear();

	    // NOR SCD1 [HW + 8H + 8W - 6 - 4K]
	    w = add_not(w - 1);
	    // NOR SCD2 [HW + 8H + 8W - 5 - 4K]
	    w = add_not(w - 1);

	    // AND OCD1, NOSCD2
	    temp.push_back(w);
	    temp.push_back(w - 5);
	    w = add_and(temp);
	    temp.clear();

	    // AND OCD2, NOSCD1
	    temp.push_back(w - 2);
	    temp.push_back(w - 5);
	    w = add_and(temp);
	    temp.clear();
    }

    // Answer
    temp.push_back(w);
    temp.push_back(w - 1);
    w = add_or(temp);
}

/*
void construct_network(int H, int W, int K) // K(H + W) + 2K + 1.. (somthlikethat) (Sub 1 .. 7) exc. 4 and 5, 5 can be recovered by setting i = K.
{
	for (int i = 0; i < H; i++)
	{
		for (int j = W * i; j < W * (i + 1); j++) temp.push_back(j);
		w = add_or(temp);
		temp.clear();
	}
	for (int i = 0; i < W; i++)
	{
		for (int j = i; j < H * W; j += W) temp.push_back(j);
		w = add_or(temp);
		temp.clear();
	}
	for (int j = H * W; j < H * W + H; j++) temp.push_back(j);
	w = hp[0] = add_xor(temp);
	temp.clear();
	for (int j = H * W + H; j < H * W + H + W; j++) temp.push_back(j);
	w = vp[0] = add_xor(temp);
	temp.clear();
	for (int i = 1; i <= K; i++)
	{
		int bef = w;
		for (int j = H * W + i; j < H * W + H; j++)
		{
			temp.push_back(j); temp.push_back(j - i);
			w = add_and(temp);
			temp.clear();
		}
		if (w != bef)
		{
			for (int i = bef + 1; i <= w; i++) {temp.push_back(i);}
			w = add_or(temp);
			temp.clear();
			hp[i] = w;
		}
	}
	//cout << "HERE\n";
	for (int i = 1; i <= K; i++)
	{
		int bef = w;
		for (int j = H * W + H + i; j < H * W + H + W; j++)
		{
			temp.push_back(j); temp.push_back(j - i);
			w = add_and(temp);
			temp.clear();
		}
		if (w != bef)
		{
			for (int i = bef + 1; i <= w; i++) {temp.push_back(i);}
			w = add_or(temp);
			temp.clear();
			vp[i] = w;
		}
	}
	int bef = w;
	for (int i = 0; i <= K; i++)
	{
		if (vp[i] && hp[K - i])
		{
			temp.push_back(vp[i]);
			temp.push_back(hp[K - i]);
			w = add_and(temp);
			temp.clear();
		}
	}
	for (int i = bef + 1; i <= w; i++) temp.push_back(i);
	w = add_or(temp);

}
*/

/*
void construct_network(int H, int W, int K) // Sub-6
{
   for (int i = 0; i <= K; i++)
   {
   	  if (i < H && K - i < W)
   	  {
   	  	 temp.push_back(i * W + K - i);
   	  }
   }
   w = add_or(temp);
}
*/

• 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