Submission #1154808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154808		Pacybwoah	Vision Program (IOI19_vision)	C++20	100 / 100	6 ms	2120 KiB

vision

#include "vision.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<utility>
#include<cassert>
using namespace std;
// i * W + j
void construct_network(int h, int w, int k) {
	vector<int> ask;
	int n = max(h, w);
	auto get = [&](int i, int j){
		return i * w + j;
	};
	auto get_ch = [&](int i, int j){
		return make_pair(i + j, i - j);
		// {0 - (2n - 2), -(n - 1) - (n - 1)}
	};
	vector<vector<int>> xs(2 * n + 1), ys(2 * n + 1), tmp;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			auto [nx, ny] = get_ch(i, j);
			xs[nx].push_back(get(i, j));
			ys[ny + n].push_back(get(i, j));
		}
	}
	for(auto &vec: xs){
		if(!vec.empty()) tmp.push_back(vec);
	}
	xs = tmp;
	vector<vector<int>>().swap(tmp);
	for(auto &vec: ys){
		if(!vec.empty()) tmp.push_back(vec);
	}
	ys = tmp;
	int szx = (int)xs.size(), szy = (int)ys.size();
	vector<int> prex(szx), prey(szy);
	for(int i = 0; i < szx; i++) prex[i] = add_xor(xs[i]);
	for(int i = 0; i < szy; i++) prey[i] = add_xor(ys[i]);
	for(int i = 1; i < szx; i++) prex[i] = add_xor({prex[i - 1], prex[i]});
	for(int i = 1; i < szy; i++) prey[i] = add_xor({prey[i - 1], prey[i]});
	vector<int> xk, xk1;
	for(int i = 0; i + k - 1 < szx; i++) xk.push_back(add_and({prex[i], prex[i + k - 1]}));
	for(int i = 0; i + k < szx; i++) xk1.push_back(add_and({prex[i], prex[i + k]}));
	for(int i = 0; i + k - 1 < szy; i++) xk.push_back(add_and({prey[i], prey[i + k - 1]}));
	for(int i = 0; i + k < szy; i++) xk1.push_back(add_and({prey[i], prey[i + k]}));
	add_and({add_or(xk), add_not(add_or(xk1))});
	return;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp vision.cpp

• 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