Submission #1133121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133121		Math4Life2020	Land of the Rainbow Gold (APIO17_rainbow)	C++20	35 / 100	3093 ms	15052 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll INF = 1e9;

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, char* 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);
	}
}

int colour(ll ar, ll ac, ll br, ll bc) {
	ar--; ac--; br--; bc--;
	long long V = (long long)(br-ar+1)*(bc-ac+1);
	long long E = (long long)(br-ar)*(bc-ac+1)+(br-ar+1)*(bc-ac);
	long long F = (long long)(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);
}

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