제출 #724299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724299		GrandTiger1729	Vision Program (IOI19_vision)	C++17	100 / 100	26 ms	2384 KiB

vision

#include "vision.h"
#ifndef EVAL
#include "grader.cpp"
#endif

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

void construct_network(int n, int m, int K){
	auto valid = [&](int i, int j) -> int {
		return 0 <= i && i < n && 0 <= j && j < m;
	};
	auto idx = [&](int i, int j) -> int {
		return i * m + j;
	};
	int N = n + m - 1;
	vector<int> res1, res2;
	auto solve = [&](int x1, int y1, int x2, int y2, int dx, int dy){
		vector<int> a(N), b(N);
		for (int i = 0; i < N; i++){
			vector<int> qry;
			for (int j = 0; j <= i; j++){
				int xx = x1 + dx * j, yy = y1 + dy * (i - j);
				if (valid(xx, yy))
					qry.push_back(idx(xx, yy));
			}
			a[i] = add_or(qry);
		}
		for (int i = 0; i < N; i++){
			vector<int> qry;
			for (int j = 0; j <= i; j++){
				int xx = x2 - dx * j, yy = y2 - dy * (i - j);
				if (valid(xx, yy))
					qry.push_back(idx(xx, yy));
			}
			b[i] = add_or(qry);
		}
		vector<int> pa(N), pb(N);
		pa[0] = a[0], pb[0] = b[0];
		for (int i = 1; i < N; i++)
			pa[i] = add_or({pa[i - 1], a[i]});
		for (int i = 1; i < N; i++)
			pb[i] = add_or({pb[i - 1], b[i]});
		vector<int> yes, no;
		for (int i = 0; i < N; i++){
			vector<int> qry;
			if (i - K >= 0)
				qry.push_back(a[i - K]);
			if (i + K < N)
				qry.push_back(b[N - 1 - (i + K)]);
			if (qry.size())
				yes.push_back(add_and({a[i], add_or(qry)}));
		}
		for (int i = 0; i < N; i++){
			vector<int> qry;
			if (i - (K + 1) >= 0)
				qry.push_back(pa[i - (K + 1)]);
			if (i + (K + 1) < N)
				qry.push_back(pb[N - 1 - (i + (K + 1))]);
			if (qry.size())
				no.push_back(add_and({a[i], add_or(qry)}));
		}
		if (yes.size())
			res1.push_back(add_or(yes));
		if (no.size())
			res2.push_back(add_or(no));
	};
	solve(0, 0, n - 1, m - 1, 1, 1);
	solve(n - 1, 0, 0, m - 1, -1, 1);
	if (res1.empty())
		add_and({add_xor({0, 0})});
	else if (res2.empty())
		add_and({add_or(res1)});
	else
		add_and({add_or(res1), add_not(add_or(res2))});
}

• 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