Submission #54819

#	Time	Username	Problem	Language	Result	Execution time	Memory
54819		top34051	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	799 ms	37520 KiB

rainbow

//Subtask 3

#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;

struct rect {
    int r1,c1,r2,c2;
    rect (int _r1 = 0, int _c1 = 0, int _r2 = 0, int _c2 = 0) {
        r1 = _r1; c1 = _c1; r2 = _r2; c2 = _c2;
    }
};

int n,m,k;
pii a[maxn];

int cx[5] = {0,0,1,-1};
int cy[5] = {1,-1,0,0};

set<pii> ban, good;

int r1,c1,r2,c2;
set<pii> vis;

vector<rect> group;

void dfs(int x, int y) {
    r1 = min(r1, x); r2 = max(r2, x);
    c1 = min(c1, y); c2 = max(c2, y);
    vis.insert({x,y});
    for(int i=-1;i<=1;i++) {
        for(int j=-1;j<=1;j++) {
            pii t = {x+i, y+j};
            if(good.find(t)==good.end()) continue;
            if(vis.find(t)!=vis.end()) continue;
            dfs(x+i, y+j);
        }
    }
}

void init(int R, int C, int sr, int sc, int M, char *s) {
	n = R; m = C; k = M;
	a[1] = {sr, sc};
	for(int i=0;i<k;i++) {
        a[i+2] = a[i+1];
		if(s[i]=='N') a[i+2].X--;
		if(s[i]=='E') a[i+2].Y++;
		if(s[i]=='W') a[i+2].Y--;
		if(s[i]=='S') a[i+2].X++;
	}
	k++;
	for(int i=1;i<=k;i++) {
        ban.insert({a[i].X,a[i].Y});
//        printf("ban %d %d\n",a[i].X,a[i].Y);
	}

    for(int i=1;i<=k;i++) {
        for(int j=0;j<4;j++) {
            pii t = {a[i].X + cx[j], a[i].Y + cy[j]};
            if(ban.find(t)!=ban.end()) continue;
            if(good.find(t)!=good.end()) continue;
            good.insert(t);
//            printf("good %d %d\n",t.X,t.Y);
        }
    }

    for(auto t : good) {
        if(vis.find(t)!=vis.end()) continue;
        r1 = r2 = t.X;
        c1 = c2 = t.Y;
        dfs(t.X,t.Y);
        group.push_back(rect(r1,c1,r2,c2));
//        printf("(%d, %d) (%d, %d)\n",r1,c1,r2,c2);
    }
}

int colour(int ar, int ac, int br, int bc) {
    int ok = 0;
    for(auto t : good) {
        if(ar<=t.X && t.X<=br && ac<=t.Y && t.Y<=bc) ok = 1;
    }
    int res = 0, cnt = 0;
    for(auto t : group) {
        if(ar<t.r1 && t.r2<br && ac<t.c1 && t.c2<bc) res++;
    }
    for(int i=ac;i<bc;i++) {
        if(good.find({ar,i})!=good.end() && ban.find({ar,i+1})!=ban.end()) cnt++;
        if(good.find({ar,i+1})!=good.end() && ban.find({ar,i})!=ban.end()) cnt++;
    }
    for(int i=ac;i<bc;i++) {
        if(good.find({br,i})!=good.end() && ban.find({br,i+1})!=ban.end()) cnt++;
        if(good.find({br,i+1})!=good.end() && ban.find({br,i})!=ban.end()) cnt++;
    }
    for(int i=ar;i<br;i++) {
        if(good.find({i,ac})!=good.end() && ban.find({i+1,ac})!=ban.end()) cnt++;
        if(good.find({i+1,ac})!=good.end() && ban.find({i,ac})!=ban.end()) cnt++;
    }
    for(int i=ar;i<br;i++) {
        if(good.find({i,bc})!=good.end() && ban.find({i+1,bc})!=ban.end()) cnt++;
        if(good.find({i+1,bc})!=good.end() && ban.find({i,bc})!=ban.end()) cnt++;
    }
    return max(ok, res + cnt/2);
}

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