oj.uz

Submission #422949

# Submission time Handle Problem Language Result Execution time Memory
422949 2021-06-10T14:40:00 Z QCFium Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 95 ms 4480 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;
	}
	return 0;
}

Subtask #1
0 / 11.0

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

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 62 ms 3840 KB Output is correct
4 Correct 88 ms 4108 KB Output is correct
5 Correct 95 ms 4152 KB Output is correct
6 Correct 70 ms 4292 KB Output is correct
7 Correct 73 ms 4480 KB Output is correct
8 Correct 62 ms 3908 KB Output is correct
9 Correct 73 ms 4028 KB Output is correct
10 Correct 75 ms 4212 KB Output is correct
11 Correct 73 ms 4276 KB Output is correct
12 Correct 61 ms 3908 KB Output is correct
13 Correct 65 ms 3888 KB Output is correct
14 Correct 63 ms 4160 KB Output is correct
15 Correct 67 ms 4204 KB Output is correct
16 Correct 63 ms 3960 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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