Submission #159811

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
159811	2019-10-24T21:54:07 Z	Jatana	Land of the Rainbow Gold (APIO17_rainbow)	C++17	35 / 100	3000 ms	10096 KB

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.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	504 KB	Output is correct
2	Correct	34 ms	504 KB	Output is correct
3	Correct	8 ms	408 KB	Output is correct
4	Correct	11 ms	376 KB	Output is correct
5	Correct	54 ms	504 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	19 ms	504 KB	Output is correct
12	Correct	45 ms	504 KB	Output is correct
13	Correct	49 ms	504 KB	Output is correct
14	Correct	72 ms	636 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Execution timed out	3044 ms	6268 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	159 ms	9848 KB	Output is correct
3	Correct	170 ms	9992 KB	Output is correct
4	Correct	196 ms	9880 KB	Output is correct
5	Correct	110 ms	7544 KB	Output is correct
6	Correct	49 ms	4472 KB	Output is correct
7	Correct	97 ms	8648 KB	Output is correct
8	Correct	89 ms	9164 KB	Output is correct
9	Correct	88 ms	8184 KB	Output is correct
10	Correct	40 ms	3960 KB	Output is correct
11	Correct	70 ms	5112 KB	Output is correct
12	Correct	194 ms	9824 KB	Output is correct
13	Correct	159 ms	9848 KB	Output is correct
14	Correct	186 ms	10012 KB	Output is correct
15	Correct	120 ms	7544 KB	Output is correct
16	Correct	42 ms	3960 KB	Output is correct
17	Correct	91 ms	8568 KB	Output is correct
18	Correct	109 ms	9980 KB	Output is correct
19	Correct	154 ms	9976 KB	Output is correct
20	Correct	172 ms	10096 KB	Output is correct
21	Correct	100 ms	9152 KB	Output is correct
22	Correct	92 ms	8184 KB	Output is correct
23	Correct	41 ms	3960 KB	Output is correct
24	Correct	68 ms	5112 KB	Output is correct
25	Correct	198 ms	9976 KB	Output is correct
26	Correct	168 ms	9884 KB	Output is correct
27	Correct	238 ms	9980 KB	Output is correct
28	Correct	111 ms	7544 KB	Output is correct
29	Correct	77 ms	3856 KB	Output is correct
30	Correct	91 ms	8824 KB	Output is correct
31	Correct	106 ms	9976 KB	Output is correct
32	Correct	163 ms	9952 KB	Output is correct
33	Correct	162 ms	9976 KB	Output is correct

Subtask #4
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	504 KB	Output is correct
2	Correct	34 ms	504 KB	Output is correct
3	Correct	8 ms	408 KB	Output is correct
4	Correct	11 ms	376 KB	Output is correct
5	Correct	54 ms	504 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	19 ms	504 KB	Output is correct
12	Correct	45 ms	504 KB	Output is correct
13	Correct	49 ms	504 KB	Output is correct
14	Correct	72 ms	636 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Execution timed out	3031 ms	5844 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	504 KB	Output is correct
2	Correct	34 ms	504 KB	Output is correct
3	Correct	8 ms	408 KB	Output is correct
4	Correct	11 ms	376 KB	Output is correct
5	Correct	54 ms	504 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	19 ms	504 KB	Output is correct
12	Correct	45 ms	504 KB	Output is correct
13	Correct	49 ms	504 KB	Output is correct
14	Correct	72 ms	636 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Execution timed out	3031 ms	5844 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Submission #159811

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 12.0

Subtask #3 24.0 / 24.0

Subtask #4 0 / 27.0

Subtask #5 0 / 26.0

Subtask #1
11.0 / 11.0

Subtask #2
0 / 12.0

Subtask #3
24.0 / 24.0

Subtask #4
0 / 27.0

Subtask #5
0 / 26.0