Submission #422954

#	Time	Username	Problem	Language	Result	Execution time	Memory
422954		QCFium	Land of the Rainbow Gold (APIO17_rainbow)	C++14	23 / 100	79 ms	3892 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;
	} else if (map_raw.size()) {
		std::vector<std::vector<bool> > used(map_raw.size(), std::vector<bool>(map_raw[0].size()));
		std::queue<std::pair<int, int> > que;
		int res = 0;
		for (int x = x0; x < x1; x++) for (int y = y0; y < y1; y++) if (!used[x][y] && map_raw[x][y]) {
			used[x][y] = true;
			res++;
			que.push({x, y});
			while (que.size()) {
				auto i = que.front();
				que.pop();
				std::pair<int, int> dd[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
				for (auto d : dd) {
					int x = i.first + d.first;
					int y = i.second + d.second;
					if (x < x0 || x >= x1 || y < y0 || y >= y1) continue;
					if (!map_raw[x][y] || used[x][y]) continue;
					used[x][y] = true;
					que.push({x, y});
				}
			}
		}
		return res;
	}
	return 0;
}

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