Submission #422949

#	Time	Username	Problem	Language	Result	Execution time	Memory
422949		QCFium	Land of the Rainbow Gold (APIO17_rainbow)	C++14	12 / 100	95 ms	4480 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"

std::vector<std::vector<bool> > map_raw;
std::vector<std::pair<int, int> > blanks;
std::vector<std::pair<int, int> > blanks0;
std::vector<std::pair<int, int> > blanks1;
bool flag0 = false;


void init(int h, int w, int sx, int sy, int m, char *s) {
	sx--;
	sy--;
	auto create_raw = [&] () {
		map_raw.resize(h, std::vector<bool>(w, true));
		int x = sx;
		int y = sy;
		map_raw[x][y] = false;
		for (int i = 0; i < m; i++) {
			if (s[i] == 'N') x--;
			if (s[i] == 'S') x++;
			if (s[i] == 'W') y--;
			if (s[i] == 'E') y++;
			map_raw[x][y] = false;
		}
	};;
	if (h <= 50 && w <= 50) {
		create_raw();
	}
	if (h == 2) {
		create_raw();
		{
			int last = -1;
			int prev = 0;
			for (int i = 0; i <= w; i++) {
				int cur = i < w ? (map_raw[0][i] | ((int) map_raw[1][i] << 1)) : 0;
				// std::cerr << "! " << cur << " " << prev << std::endl;
				if (prev & cur) {
					prev = cur;
					continue;
				}
				if (prev) blanks.push_back({last, i - 1});
				if (cur) last = i;
				prev = cur;
			}
		}
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < w; ) {
				if (!map_raw[i][j]) j++;
				else {
					int t = j;
					while (j < w && map_raw[i][j]) j++;
					(i ? blanks1 : blanks0).push_back({t, j - 1});
				}
			}
		}
		flag0 = true;
	}
}

int colour(int x0, int y0, int x1, int y1) {
	/*
	for (auto i : blanks) std::cerr << i.first << "," << i.second << "  ";
	std::cerr << std::endl;
	for (auto i : blanks0) std::cerr << i.first << "," << i.second << "  ";
	std::cerr << std::endl;
	for (auto i : blanks1) std::cerr << i.first << "," << i.second << "  ";
	std::cerr << std::endl;*/
	x0--;
	y0--;
	if (flag0) {
		auto &target = x1 == 1 ? blanks0 : x0 == 1 ? blanks1 : blanks;
		auto itr0 = std::lower_bound(target.begin(), target.end(), std::pair<int, int>{y0, -1});
		if (itr0 != target.begin() && std::prev(itr0)->second >= y0) itr0--;
		auto itr1 = std::lower_bound(target.begin(), target.end(), std::pair<int, int>{y1, -1});
		return itr1 - itr0;
	}
	return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26