제출 #159811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159811		Jatana	무지개나라 (APIO17_rainbow)	C++17	35 / 100	3044 ms	10096 KiB

rainbow

#ifndef __RAINBOW_H
#define __RAINBOW_H

#include "rainbow.h"
#include <iostream>
#include <cassert>
#include <string>
#include <set>
#include <string>
#include <algorithm>
#define mp make_pair
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

string dirs = "NSWE";
int id(char c) {
	return find(dirs.begin(), dirs.end(), c) - dirs.begin();
}
pii shs[4] = {
	mp(-1, 0),
	mp(1, 0),
	mp(0, -1),
	mp(0, 1)
};

set<pii> edges[4];
set<pii> Qu;
set<pii> forb;

void init(int R, int C, int sr, int sc, int M, char *S) {
	assert(forb.empty());
	sr++, sc++;
	forb.emplace(sr, sc);
	for (int i = 0; i < M; i++) {
		sr += shs[id(S[i])].x;
		sc += shs[id(S[i])].y;
		forb.emplace(sr, sc);
	}
	for (pii ceil : forb) {
		if (forb.count(mp(ceil.x, ceil.y + 1)))
			edges[0].insert(ceil);
		if (forb.count(mp(ceil.x - 1, ceil.y)))
			edges[2].insert(ceil);
		if (forb.count(mp(ceil.x - 1, ceil.y + 1))
			&& (!forb.count(mp(ceil.x - 1, ceil.y)) && !forb.count(mp(ceil.x, ceil.y + 1))))
			edges[1].insert(ceil);
		if (forb.count(mp(ceil.x - 1, ceil.y - 1))
			&& (!forb.count(mp(ceil.x - 1, ceil.y)) && !forb.count(mp(ceil.x, ceil.y - 1))))
			edges[3].insert(ceil);
		bool fail = false;
		for (pii sh : {
			mp(1, 0),
			mp(1, 1),
			mp(0, 1)
		}) {
			if (!forb.count(mp(ceil.x + sh.x, ceil.y + sh.y)))
				fail = true;
		}
		if (!fail) Qu.insert(ceil);
	}
}

int colour(int ar, int ac, int br, int bc) {
	ar++, ac++, br++, bc++;
	int V = 0;
	int E = 0;
	auto in = [ar, ac, br, bc](pii ceil) {
		return (ar <= ceil.x && ceil.x <= br
			&& ac <= ceil.y && ceil.y <= bc);
	};
	for (pii fb : forb)
		if (in(fb))
			V++;
	for (pii p : edges[0])
		if (in(p) && in(mp(p.x, p.y + 1)))
			E++;
	for (pii p : edges[2])
		if (in(p) && in(mp(p.x - 1, p.y)))
			E++;
	for (pii p : edges[1])
		if (in(p) && in(mp(p.x - 1, p.y + 1)))
			E++;
	for (pii p : edges[3])
		if (in(p) && in(mp(p.x - 1, p.y - 1)))
			E++;
	int Q = 0;
	for (pii q : Qu)
		if (in(q) && q.x < br && q.y < bc)
			Q++;
	int hit = 0;
	int cnt = 0;
	for (pii fb : forb) {
		if (in(fb)) {
			cnt = 1;
			bool is_row = (fb.x == ar || fb.x == br);
			bool is_col = (fb.y == ac || fb.y == bc);
			if (is_row || is_col) hit = 1;
			if (fb.x == ar) E++;
			if (fb.x == br) E++;
			if (fb.y == ac) E++;
			if (fb.y == bc) E++;
			if (fb.x == ar)
				if (fb.y + 1 <= bc && forb.count(mp(fb.x, fb.y + 1)))
					Q++;
			if (fb.x == br)
				if (fb.y + 1 <= bc && forb.count(mp(fb.x, fb.y + 1)))
					Q++;
			if (fb.y == ac)
				if (fb.x + 1 <= br && forb.count(mp(fb.x + 1, fb.y)))
					Q++;
			if (fb.y == bc)
				if (fb.x + 1 <= br && forb.count(mp(fb.x + 1, fb.y)))
					Q++;
			if (fb.x == ar && fb.y == ac) Q++;
			if (fb.x == ar && fb.y == bc) Q++;
			if (fb.x == br && fb.y == ac) Q++;
			if (fb.x == br && fb.y == bc) Q++;
		}
	}
	if (cnt && hit) cnt--;
    return 1 - V + E - Q + cnt;
}


#endif  // __RAINBOW_H

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