Submission #298539

#	Time	Username	Problem	Language	Result	Execution time	Memory
298539		JPN20	Vision Program (IOI19_vision)	C++17	100 / 100	35 ms	3580 KiB

vision

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

vector<int> v1[409];
vector<int> v2[409];

void Reigai(int H, int W, int K) {
	add_and(vector<int>{0, H * W - 1});
	add_and(vector<int>{(H - 1) * W, W - 1});
	add_or(vector<int>{H * W + 0, H * W + 1});
}

void construct_network(int H, int W, int K) {
	for (int i = 0; i < 409; i++) v1[i].clear();
	for (int i = 0; i < 409; i++) v2[i].clear();
	
	if (K == H + W - 2) {
		Reigai(H, W, K);
		return;
	}
	
	// Step #1. Maeshori
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int c1 = i + j;
			int c2 = i - j + (W - 1);
			v1[c1].push_back(i * W + j);
			v2[c2].push_back(i * W + j);
		}
	}
	
	// Step #2. Query 1
	int cnt = H * W;
	int milestone1 = cnt;
	for (int i = 0; i <= H + W - 2; i++) { add_or(v1[i]); cnt++; }
	
	// Step #3. Query 2
	int milestone2 = cnt;
	for (int i = 0; i <= H + W - 2; i++) { add_or(v2[i]); cnt++; }
	
	// Step #4. Query 3 (Ruisekiwa)
	int milestone3 = cnt;
	for (int i = 0; i <= H + W - 2; i++) {
		vector<int> vec;
		for (int j = 0; j <= i; j++) vec.push_back(milestone1 + j);
		add_or(vec); cnt++;
	}
	
	// Step #5. Query 4 (Ruisekiwa)
	int milestone4 = cnt;
	for (int i = 0; i <= H + W - 2; i++) {
		vector<int> vec;
		for (int j = 0; j <= i; j++) vec.push_back(milestone2 + j);
		add_or(vec); cnt++;
	}
	
	// Step #6. PreFinal
	vector<int> vec1;
	for (int i = 0; i <= H + W - 2 - (K + 1); i++) {
		vec1.push_back(cnt);
		int c1 = milestone3 + i;
		int c2 = milestone1 + i + (K + 1);
		add_and(vector<int>{c1, c2});
		cnt++;
	}
	vector<int> vec2;
	for (int i = 0; i <= H + W - 2 - (K + 1); i++) {
		vec2.push_back(cnt);
		int c1 = milestone4 + i;
		int c2 = milestone2 + i + (K + 1);
		add_and(vector<int>{c1, c2});
		cnt++;
	}
	vector<int> vec3;
	for (int i = 0; i <= H + W - 2 - K; i++) {
		vec3.push_back(cnt);
		int c1 = milestone1 + i;
		int c2 = milestone1 + i + K;
		add_and(vector<int>{c1, c2});
		cnt++;
	}
	vector<int> vec4;
	for (int i = 0; i <= H + W - 2 - K; i++) {
		vec4.push_back(cnt);
		int c1 = milestone2 + i;
		int c2 = milestone2 + i + K;
		add_and(vector<int>{c1, c2});
		cnt++;
	}
	
	// Step #7. Final
	int base = cnt;
	add_or(vec1);
	add_or(vec2);
	add_or(vec3);
	add_or(vec4);
	add_not(base + 0);
	add_not(base + 1);
	add_or(vector<int>{base + 2, base + 3});
	add_and(vector<int>{base + 4, base + 5, base + 6});
}

• 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