Submission #153479

#	Time	Username	Problem	Language	Result	Execution time	Memory
153479		myungwoo	Vision Program (IOI19_vision)	C++14	100 / 100	17 ms	1804 KiB

vision

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

void construct_network(int H, int W, int K)
{
	vector <int> arr;
	for (int i=0;i<H;i++){
		vector <int> row;
		for (int j=0;j<W;j++) row.push_back(i*W+j);
		int row_xor = add_xor(row);
		if (i == 0) arr.push_back(row_xor);
		else arr.push_back(add_xor({arr.back(), row_xor}));
	}
	for (int j=0;j<W;j++){
		vector <int> col;
		for (int i=0;i<H;i++) col.push_back(i*W+j);
		int col_xor = add_xor(col);
		if (j == 0) arr.push_back(col_xor);
		else arr.push_back(add_xor({arr.back(), col_xor}));
	}
	// 여기서 arr에 있는 1비트 개수가 두 점의 맨하탄 거리

	int max_dist = H+W-2, zero = arr.back();
	vector <int> bits;
	for (int i=0;(1<<i)<=max_dist;i++){
		bits.push_back(add_xor(arr));

		// arr에 있는 1비트들을 홀짝 여부에 따라 01 반복으로 바꿔주기
		int v = zero;
		vector <int> tmp;
		for (int j=0;j<H+W;j++){
			tmp.push_back(add_and({v, arr[j]}));
			v = add_xor({v, arr[j]});
		}
		arr = tmp;
	}
	for (int i=0;i<bits.size();i++) if (!(K & 1<<i)) bits[i] = add_not(bits[i]);
	add_and(bits);
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<bits.size();i++) if (!(K & 1<<i)) bits[i] = add_not(bits[i]);
               ~^~~~~~~~~~~~

• 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