Submission #830419

#	Time	Username	Problem	Language	Result	Execution time	Memory
830419		pavement	Vision Program (IOI19_vision)	C++17	100 / 100	66 ms	7896 KiB

vision

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

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

using ii = pair<int, int>;

void construct_network(int H, int W, int K) {
	auto conv = [&](int r, int c) {
		return r * W + c;
	};
	vector<int> row(H + W - 1), row2(H + W - 1), col(H + W - 1), col2(H + W - 1);
	vector<vector<int> > rows(H + W - 1), cols(H + W - 1);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			rows[i - j + W - 1].pb(conv(i, j));
			cols[i + j].pb(conv(i, j));
		}
	}
	int ins = H * W;
	vector<int> tmp(H * W);
	iota(tmp.begin(), tmp.end(), 0);
	add_or(tmp);
	int ONE = ins++;
	vector<int> last;
	for (int i = 0; i < H + W - 1; i++) {
		for (auto [vec, addr, addr2] : {mt(rows[i], &row[i], &row2[i]), mt(cols[i], &col[i], &col2[i])}) {
			assert(!vec.empty());
			add_or(vec);
			*addr = ins++;
			vec.pb(ONE);
			add_xor(vec);
			ins++;
			vec.pop_back();
			add_and({ins - 1, ins - 2});
			*addr2 = ins++;
		}
	}
	for (int reps = 0; reps < 2; reps++, K--) {
		vector<int> fin_row(2 * (H + W - 1 - K)), fin_col(2 * (H + W - 1 - K));
		for (auto [vec, vec2, fin] : {mt(row, row2, &fin_row), mt(col, col2, &fin_col)}) {
			for (int i = 0; i + K < H + W - 1; i++) {
				vector<int> cur, cur2;
				for (int j = i; j <= i + K; j++) {
					cur.pb(vec[j]);
					cur2.pb(vec2[j]);
				}
				add_or(cur);
				ins++;
				cur.pb(ONE);
				add_xor(cur);
				ins++;
				cur.pop_back();
				add_and({ins - 1, ins - 2});
				ins++;
				add_or(cur2);
				ins++;
				(*fin)[2 * i] = ins - 1;
				(*fin)[2 * i + 1] = ins - 2;
			}
		}
		add_or(fin_row);
		add_or(fin_col);
		ins += 2;
		add_and({ins - 2, ins - 1});
		last.pb(ins++);
	}
	add_xor(last);
}

• 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