| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 159794 | Jatana | Land of the Rainbow Gold (APIO17_rainbow) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#ifndef __RAINBOW_H
#define __RAINBOW_H
#include "rainbow.h"
#include <iostream>
#include <string>
#include <set>
#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++;
// cout << ar << " " << br << " " << ac << " " << bc << endl;
int Q = 0;
for (pii fb : forb)
if (in(fb) && Qu.count(fb)
&& fb.x < br && fb.y < bc)
Q++;
// cout << "!" << Q << endl;
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 (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++;
}
}
// cout << V << " " << E << " " << Q << endl;
return 1 - V + E - Q;
}
#endif // __RAINBOW_H