Submission #995472

#	Time	Username	Problem	Language	Result	Execution time	Memory
995472		thinknoexit	Vision Program (IOI19_vision)	C++17	100 / 100	33 ms	6104 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[202][202];
int pos[404], neg[404];
int npos[404], nneg[404];
int s1, s2;
vector<int> Q1[404], Q2[404];
int n, m;
int solve(int K) {
	if (K == 1) return add_and({ s1, s2 });
	vector<int> QQ1, QQ2;
	QQ1.push_back(s1);
	QQ2.push_back(s2);
	for (int i = 1;i <= n + m - 2;i++) {
		vector<int> Q1, Q2;
		for (int j = max(0, i - K + 1);j < i;j++) {
			Q1.push_back(pos[j]);
			Q2.push_back(neg[j]);
		}
		QQ1.push_back(add_and({ pos[i], add_or(Q1) }));
		QQ2.push_back(add_and({ neg[i], add_or(Q2) }));
	}
	return add_and({ add_or(QQ1), add_or(QQ2) });
}
void construct_network(int H, int W, int K) {
	n = H, m = W;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			a[i][j] = i * m + j;
			Q1[i + j].push_back(a[i][j]);
			Q2[i - j + m - 1].push_back(a[i][j]);
		}
	}
	for (int i = 0;i <= n + m - 2;i++) pos[i] = add_or(Q1[i]);
	for (int i = 0;i <= n + m - 2;i++) neg[i] = add_or(Q2[i]);
	for (int i = 0;i <= n + m - 2;i++) npos[i] = add_xor({ pos[i], add_xor(Q1[i]) });
	for (int i = 0;i <= n + m - 2;i++) nneg[i] = add_xor({ neg[i], add_xor(Q2[i]) });
	{
		vector<int> Q;
		for (int i = 0;i <= n + m - 2;i++) Q.push_back(npos[i]);
		s1 = add_or(Q);
	}
	{
		vector<int> Q;
		for (int i = 0;i <= n + m - 2;i++) Q.push_back(nneg[i]);
		s2 = add_or(Q);
	}
	add_and({ add_not(solve(K)), solve(K + 1) });
}

• 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