Submission #569289

#	Time	Username	Problem	Language	Result	Execution time	Memory
569289		pavement	Vision Program (IOI19_vision)	C++17	58 / 100	684 ms	1172 KiB

vision

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

#define pb push_back

int or_row[205], or_col[205], can_row[205], can_col[205];

void construct_network(int H, int W, int K) {
	int ops = 0;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			for (int k = i + 1; k < H; k++)
				for (int l = 0; l < W; l++)
					if (abs(i - k) + abs(j - l) == K) {
						vector<int> tmp = {i * W + j, k * W + l};
						ops++;
						//add_and(tmp);
					}
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			for (int k = i; k <= i; k++)
				for (int l = j + 1; l < W; l++)
					if (abs(i - k) + abs(j - l) == K) {
						vector<int> tmp = {i * W + j, k * W + l};
						ops++;
						//add_and(tmp);
					}
	if (2 * ops <= 10000) {
		ops = 0;
		for (int i = 0; i < H; i++)
			for (int j = 0; j < W; j++)
				for (int k = i + 1; k < H; k++)
					for (int l = 0; l < W; l++)
						if (abs(i - k) + abs(j - l) == K) {
							vector<int> tmp = {i * W + j, k * W + l};
							ops++;
							add_and(tmp);
						}
		for (int i = 0; i < H; i++)
			for (int j = 0; j < W; j++)
				for (int k = i; k <= i; k++)
					for (int l = j + 1; l < W; l++)
						if (abs(i - k) + abs(j - l) == K) {
							vector<int> tmp = {i * W + j, k * W + l};
							ops++;
							add_and(tmp);
						}
		vector<int> tmp;
		for (int i = 0; i < ops; i++)
			tmp.push_back(H * W + i);
		add_or(tmp);
		return;
	}

	int cnt = H * W;
	for (int i = 0; i < H; i++) {
		vector<int> tmp;
		for (int j = 0; j < W; j++)
			tmp.pb(i * W + j);
		add_or(tmp);
		or_row[i] = cnt++;
	}
	for (int j = 0; j < W; j++) {
		vector<int> tmp;
		for (int i = 0; i < H; i++)
			tmp.pb(i * W + j);
		add_or(tmp);
		or_col[j] = cnt++;
	}
	
	for (int ver = 1; ver <= K; ver++) {
		if (ver >= H || K - ver >= W) continue;
		vector<int> tmp2;
		for (int i = 0; i + ver < H; i++) {
			vector<int> tmp = {or_row[i], or_row[i + ver]};
			add_and(tmp);
			//cout << "@ " << ver << ' ' << i << ' ' << cnt << '\n';
			tmp2.pb(cnt++);
		}
		add_or(tmp2);
		can_row[ver] = cnt++;
	}
	
	vector<int> bruh;
	
	if (K < W) {
		for (int i = 0; i < H; i++)
			bruh.pb(or_row[i]);
		add_xor(bruh);
		can_row[0] = cnt++;
	}
	
	for (int hor = 1; hor <= K; hor++) {
		if (hor >= W || K - hor >= H) continue;
		vector<int> tmp2;
		int ocnt = cnt, tmpp = 0;
		for (int i = 0; i + hor < W; i++) {
			vector<int> tmp = {or_col[i], or_col[i + hor]};
			add_and(tmp);
			//cout << "@ " << hor << ' ' << i << ' ' << cnt << '\n';
			tmp2.pb(cnt++);
		}
		add_or(tmp2);
		can_col[hor] = cnt++;
	}
	
	if (K < H) {
		bruh.clear();
		for (int i = 0; i < W; i++)
			bruh.pb(or_col[i]);
		add_xor(bruh);
		can_col[0] = cnt++;
	}
	
	//cout << "@" << cnt << " " << can_row[1] << ' ' << can_col[0] << '\n';

	vector<int> tot;
	for (int ver = 0; ver <= K; ver++) {
		int hor = K - ver;
		if (ver < H && hor < W) {
			vector<int> tmp = {can_row[ver], can_col[hor]};
			add_and(tmp);
			tot.pb(cnt++);
		}
	}
	add_or(tot);
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:97:7: warning: unused variable 'ocnt' [-Wunused-variable]
   97 |   int ocnt = cnt, tmpp = 0;
      |       ^~~~
vision.cpp:97:19: warning: unused variable 'tmpp' [-Wunused-variable]
   97 |   int ocnt = cnt, tmpp = 0;
      |                   ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 15
• Subtask 5: 12 / 12
• Subtask 6: 0 / 8
• Subtask 7: 14 / 14
• Subtask 8: 0 / 19