oj.uz

Submission #159798

# Submission time Handle Problem Language Result Execution time Memory
159798 2019-10-24T16:40:41 Z Jatana Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 176 ms 9976 KB 
#ifndef __RAINBOW_H
#define __RAINBOW_H

#include "rainbow.h"
#include <iostream>
#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) {
	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++;
	bool hit = false;
	for (pii fb : forb) {
		if (in(fb)) {
			bool is_row = (fb.x == ar || fb.x == br);
			bool is_col = (fb.y == ac || fb.y == bc);
			if (is_row || is_col) hit = true;
			if (fb.x == ar) E++;
			if (fb.x == br) E++;
			if (fb.y == ac) E++;
			if (fb.y == bc) E++;
			if (is_row)
				if (fb.y + 1 <= bc && forb.count(mp(fb.x, fb.y + 1)))
					Q++;
			if (is_col)
				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++;
		}
	}
    return 1 - V + E - Q + (1 - hit);
}


#endif  // __RAINBOW_H

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 157 ms 9848 KB Output is correct
3 Correct 154 ms 9836 KB Output is correct
4 Correct 176 ms 9976 KB Output is correct
5 Correct 118 ms 7772 KB Output is correct
6 Incorrect 52 ms 4600 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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