Submission #260191

#	Time	Username	Problem	Language	Result	Execution time	Memory
260191		user202729	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3082 ms	1048580 KiB

rainbow

// moreflags=grader.cpp
// 6
// :(
#include "rainbow.h"
#include<set>
#if not LOCAL
#define NDEBUG
#endif
#include<vector>
#include<cassert>

namespace{
	int R, C;
	std::set<std::pair<int, int>> cells;
	std::vector<std::vector<char>> have;
}

void init(int R_, int C_, int sr, int sc, int M, char *S) {
	R=R_; C=C_;
	cells.clear();
	--sr;--sc;
	cells.insert({sr, sc});
	for(int i=0; i<M; ++i){
		switch(S[i]){
			case 'N': --sr; break;
			case 'W': --sc; break;
			case 'E': ++sc; break;
			case 'S': ++sr; break;
			default: assert(false); __builtin_unreachable();
		}
		cells.insert({sr, sc});
	}

	have.assign(R, std::vector<char>(C, 0));
	for(auto [r, c]: cells) have[r][c]=1;
}

int colour(int ar, int ac, int br, int bc) {
	--ar;--ac;

	static std::vector<std::pair<int, int>> queue;
	int front=0; queue.clear();

	for(int r=ar; r<br; ++r)
		for(int c=ac; c<bc; ++c)
			assert(have[r][c]==0 or have[r][c]==1);

	assert(ar<br); assert(ac<bc);

	int result{};
	for(int r=ar; r<br; ++r)
		for(int c=ac; c<bc; ++c)
			if(have[r][c]==0){
				++result;
				//std::array<int, 4> bounds{{r, c, r+1, c+1}};

				front=(int)queue.size();
				queue.push_back(std::make_pair(r, c));
				have[r][c]=2;
				while(front<(int)queue.size()){
					auto [r, c]=queue[front++];
					/*
					bounds[0]=std::min(bounds[0], r);
					bounds[1]=std::min(bounds[1], c);
					bounds[2]=std::max(bounds[2], r+1);
					bounds[3]=std::max(bounds[3], c+1);
					*/
					for(int _=0, a=1, b=0; _<4; ++_, std::swap(a, b), b=-b){
						if(unsigned(r+a-ar)<unsigned(br-ar) and unsigned(c+b-ac)<unsigned(bc-ac) and
								have[r+a][c+b]==0){
							have[r+a][c+b]=2;
							queue.push_back({r+a, c+b});
						}
					}
				}
				//regions
				//blocks.push_back(bounds);
			}

	for(auto [r, c]: queue) {
		assert(have[r][c]==2);
		have[r][c]=0;
	}
    return result;
}

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