| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1133113 | Math4Life2020 | Land of the Rainbow Gold (APIO17_rainbow) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;
vector<pii> vv; //snake vertices
vector<pii> vev,veh; //snake edges
//vev: (x,y) -> (x+1,y)
//veh: (x,y) -> (x,y+1)
vector<pii> vf; //snake ~internal faces
ll xsmin = INF; ll ysmin = INF; ll xsmax = -1; ll ysmax = -1;
vector<pii> clr(vector<pii> v0) {
sort(v0.begin(),v0.end());
v0.erase(unique(v0.begin(),v0.end()),v0.end());
vector<pii> v1;
for (pii p0: v0) {
if (p0.first>=0 && p0.second>=0) {
v1.push_back(p0);
}
}
return v1;
}
void init(ll R, ll C, ll sr, ll sc, ll M, string S) {
sr--; sc--;
vv.clear(); vev.clear(); veh.clear(); vf.clear();
ll x = sr; ll y = sc;
vv.push_back({x,y});
for (ll t=0;t<M;t++) {
if (S[t]=='N') {
x--;
}
if (S[t]=='S') {
x++;
}
if (S[t]=='E') {
y++;
}
if (S[t]=='W') {
y--;
}
vv.push_back({x,y});
}
for (pii p0: vv) {
ll x1 = p0.first; ll y1 = p0.second;
vev.push_back({x1,y1});
vev.push_back({x1-1,y1});
veh.push_back({x1,y1});
veh.push_back({x1,y1-1});
vf.push_back({x1,y1});
vf.push_back({x1-1,y1});
vf.push_back({x1,y1-1});
vf.push_back({x1-1,y1-1});
}
vv = clr(vv); //remove duplicates / negatives
vev = clr(vev);
veh = clr(veh);
vf = clr(vf);
for (pii p0: vv) {
xsmin = min(xsmin, p0.first);
ysmin = min(ysmin, p0.second);
xsmax = max(xsmax, p0.first);
ysmax = max(ysmax, p0.second);
}
}
ll colours(ll ar, ll ac, ll br, ll bc) {
ar--; ac--; br--; bc--;
ll V = (br-ar+1)*(bc-ac+1);
ll E = (br-ar)*(bc-ac+1)+(br-ar+1)*(bc-ac);
ll F = (br-ar)*(bc-ac); //INTERNAL faces
if (ar<xsmin && ac<ysmin && br>xsmax && bc>ysmax) {
F++;
}
//cout << "V,E,F init="<<V<<","<<E<<","<<F<<"\n";
for (pii p0: vv) {
ll x = p0.first; ll y = p0.second;
if (x>=ar && x<=br && y>=ac && y<=bc) {
V--;
}
}
for (pii p0: vev) {
ll x = p0.first; ll y = p0.second;
if (x>=ar && x<br && y>=ac && y<=bc) { //x<br strict
E--;
}
}
for (pii p0: veh) {
ll x = p0.first; ll y = p0.second;
if (x>=ar && x<=br && y>=ac && y<bc) { //y<bc strict
E--;
}
}
for (pii p0: vf) {
ll x = p0.first; ll y = p0.second;
if (x>=ar && x<br && y>=ac && y<bc) { //x<br,y<bc strict
F--;
}
}
//cout << "V,E,F final="<<V<<","<<E<<","<<F<<"\n";
return (F+V-E);
}