Submission #825982

#	Time	Username	Problem	Language	Result	Execution time	Memory
825982		caganyanmaz	Vision Program (IOI19_vision)	C++17	100 / 100	24 ms	2920 KiB

vision

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

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

int h, w, k;

static inline bool in_bounds(int i, int j)
{
	return i >= 0 && j >= 0 && i < h && j < w;
}

static inline int serialize(int i, int j)
{
	return i * w + j;
}

array<int, 2> calculate(int left_bound, int right_bound)
{
	vector<int> vals;
	for (int i = left_bound; i+k <= right_bound; i++)
	{
		if (i+k <= right_bound)
		{
			vector<int> v;
			v.pb(i);
			v.pb(i+k);
			vals.pb(add_and(v));
		}
	}
	debug(vals);
	int ek1;
	{
		vector<int> v;
		for (int i : vals)
			v.pb(i);
		ek1 = add_or(v);
	}
	debug("b");
	vector<int> _nots;
	for (int i = left_bound; i+k < right_bound; i++)
	{
		vector<int> v;
		for (int j = i+k+1; j <= right_bound; j++)
			v.pb(j);
		if (v.empty())
			continue;
		int _new = add_or(v);
		v.clear();
		v.pb(_new);
		v.pb(i);
		_nots.pb(add_and(v));// If both open its greater than
	}
	debug("c");
	int gk1;
	if (_nots.size())
	{
		gk1 = add_or(_nots);
	}
	debug("d");
	return array<int, 2> ({ek1, gk1});
}

void construct_network(int H, int W, int K)
{
	h = H, w = W, k = K;
	int left_bound = -1, right_bound = -1;
	for (int l = 0; l <= W+H; l++)
	{
		vector<int> v;
		for (int i = 0; i < h; i++)
		{
			int j = l-i;
			if (in_bounds(i, j))
				v.pb(serialize(i, j));
		}
		if (v.size() > 0)
			right_bound = add_or(v);
		if (left_bound == -1 && right_bound != -1)
			left_bound = right_bound;
	}
	auto [ek1, gk1] =calculate(left_bound, right_bound);
	left_bound = -1, right_bound = -1;
	for (int l = 0; l <= W+H; l++)
	{
		vector<int> v;
		for (int i = 0; i < h; i++)
		{
			int j = i+w-l;
			if (in_bounds(i, j))
				v.pb(serialize(i, j));
		}
		if (v.size() > 0)
			right_bound = add_or(v);
		if (left_bound == -1 && right_bound != -1)
			left_bound = right_bound;
	}
	auto [ek2, gk2] = calculate(left_bound, right_bound);
	if (k < w + h - 2)
	{
		vector<int> v;
		v.pb(gk1);
		v.pb(gk2);
		int a = add_or(v);
		int not_greater = add_not(a);
		v.clear();
		v.pb(ek1);
		v.pb(ek2);
		int equal = add_or(v);
		v.clear();
		v.pb(not_greater);
		v.pb(equal);
		add_and(v);
	}
	else
	{
		vector<int> v;
		v.pb(ek1);
		v.pb(ek2);
		add_or(v);
	}

}

Compilation message (stderr)

vision.cpp: In function 'std::array<int, 2> calculate(int, int)':
vision.cpp:67:34: warning: 'gk1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  return array<int, 2> ({ek1, gk1});
      |                                  ^

• 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