제출 #425986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425986		Mazaalai	Vision Program (IOI19_vision)	C++17	100 / 100	79 ms	7540 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
 
/*
int add_not(int N)
int add_and(int[] Ns)
int add_or(int[] Ns)
int add_xor(int[] Ns)
*/
int n, m, K;
const int N = 1005;
int st1, end1, st2, end2;
vector <vector <int> > diag1(N), diag2(N);
vector <int> diag1_or(N), diag2_or(N);
vector <int> diag1_xor(N), diag2_xor(N);
vector <int> diag1_duo(N), diag2_duo(N);
int Idx(int A, int B) {
	// nums[A][B] = (A-1)*W + B;
	return A * m + B;
}
int Dist(int a, int b, int a1, int b1) {
	return abs(a-a1)+abs(b-b1);
}
int solve(int k) {
	vector <int> pos1;
	for (int i = st1; i + k - 1 <= end1; i++) {
		vector <int> vals, vals_duo;
		for (int j = i; j <= i + k - 1; j++) {
			vals.push_back(diag1_or[j]);
			vals_duo.push_back(diag1_duo[j]);
		}
		int a, b, c, d;
		a = vals.size() > 1 ? add_or(vals) : vals[0];
		b = vals.size() > 1 ? add_xor(vals) : vals[0];
		d = vals_duo.size() > 1 ? add_or(vals_duo) : vals_duo[0];
		c = add_xor({a, b});
		pos1.push_back(add_or({c, d}));
	}
	int ans1 = pos1.size() == 1 ? pos1[0] : add_or(pos1);
	vector <int> pos2;
	for (int i = st2; i + k - 1 <= end2; i++) {
		vector <int> vals, vals_duo;
		for (int j = i; j <= i + k - 1; j++) {
			vals.push_back(diag2_or[j]);
			vals_duo.push_back(diag2_duo[j]);
		}
		int a, b, c, d;
		a = vals.size() > 1 ? add_or(vals) : vals[0];
		b = vals.size() > 1 ? add_xor(vals) : vals[0];
		d = vals_duo.size() > 1 ? add_or(vals_duo) : vals_duo[0];
		c = add_xor({a, b});
		pos2.push_back(add_or({c, d}));
	}
	int ans2 = pos2.size() == 1 ? pos2[0] : add_or(pos2);
	return add_and({ans1, ans2});
}
void construct_network(int H, int W, int K1) {
	n = H, m = W, K = K1;
	st1 = N, end1 = 0, st2 = N, end2 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int pos1 = i+j, pos2 = i-j+m, idx = Idx(i, j);
			diag1[pos1].push_back(idx);
			diag2[pos2].push_back(idx);
			st1=min(st1, pos1);
			end1=max(end1, pos1);
			st2=min(st2, pos2);
			end2=max(end2, pos2);
		}
	}
	for (int i = 0; i < N; i++) {
		if (diag1[i].size() >= 1) {
			diag1_or[i] = diag1[i].size() == 1 ? diag1[i][0] : add_or(diag1[i]);
			diag1_xor[i] = diag1[i].size() == 1 ? diag1[i][0] : add_xor(diag1[i]);
			diag1_duo[i] = add_xor({diag1_or[i], diag1_xor[i]});
		} 
		if (diag2[i].size() >= 1) {
			diag2_or[i] = diag2[i].size() == 1 ? diag2[i][0] : add_or(diag2[i]);
			diag2_xor[i] = diag2[i].size() == 1 ? diag2[i][0] : add_xor(diag2[i]);
			diag2_duo[i] = add_xor({diag2_or[i], diag2_xor[i]});
		} 
	}
	int x = solve(K+1), y = solve(K);
	add_xor({x, y});
}

• 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