oj.uz

Submission #422954

# Submission time Handle Problem Language Result Execution time Memory
422954 2021-06-10T14:44:11 Z QCFium Land of the Rainbow Gold (APIO17_rainbow) C++14
23 / 100
 79 ms 3892 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB Output is correct
2 Correct 21 ms 336 KB Output is correct
3 Correct 37 ms 204 KB Output is correct
4 Correct 39 ms 332 KB Output is correct
5 Correct 21 ms 340 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 32 ms 336 KB Output is correct
12 Correct 31 ms 332 KB Output is correct
13 Correct 29 ms 332 KB Output is correct
14 Correct 20 ms 344 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 65 ms 1080 KB Output is correct
4 Correct 68 ms 1120 KB Output is correct
5 Correct 74 ms 1476 KB Output is correct
6 Correct 70 ms 1316 KB Output is correct
7 Correct 73 ms 1568 KB Output is correct
8 Correct 60 ms 1092 KB Output is correct
9 Correct 70 ms 1092 KB Output is correct
10 Correct 79 ms 1540 KB Output is correct
11 Correct 71 ms 1364 KB Output is correct
12 Correct 57 ms 1092 KB Output is correct
13 Correct 61 ms 1152 KB Output is correct
14 Correct 71 ms 1348 KB Output is correct
15 Correct 63 ms 1392 KB Output is correct
16 Correct 61 ms 1060 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB Output is correct
2 Correct 21 ms 336 KB Output is correct
3 Correct 37 ms 204 KB Output is correct
4 Correct 39 ms 332 KB Output is correct
5 Correct 21 ms 340 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 32 ms 336 KB Output is correct
12 Correct 31 ms 332 KB Output is correct
13 Correct 29 ms 332 KB Output is correct
14 Correct 20 ms 344 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Incorrect 62 ms 3892 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB Output is correct
2 Correct 21 ms 336 KB Output is correct
3 Correct 37 ms 204 KB Output is correct
4 Correct 39 ms 332 KB Output is correct
5 Correct 21 ms 340 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 32 ms 336 KB Output is correct
12 Correct 31 ms 332 KB Output is correct
13 Correct 29 ms 332 KB Output is correct
14 Correct 20 ms 344 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Incorrect 62 ms 3892 KB Output isn't correct
19 Halted 0 ms 0 KB -