Submission #57353

#	Time	Username	Problem	Language	Result	Execution time	Memory
57353		MatheusLealV	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	195 ms	6364 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#define N 200050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, m, ok[5][N], block[5][N];

int inicio[5][N];

int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

int Ni, Mi, Nii, Mii, col;

int branco[2][N];

int dxy(char c)
{
	if(c == 'N') return 1;

	if(c == 'S') return 0;

	if(c == 'W') return 3;

	if(c == 'E') return 2;

	return -1;
}

int pref[5][N];

void dfs(int x, int y)
{
	ok[x][y] = 1;

	//cout<<"DFS "<<x<<" "<<y<<"\n";

	for(int i = 0; i < 4; i++)
	{
		int a = x + dx[i], b = y + dy[i];

		if(a < Ni or b < Mi or a > Nii or b > Mii or ok[a][b] == 1 or block[a][b]) continue;

		ok[a][b] = 1;

		dfs(a, b);
	}
}

vector < pii > zeros;

int ans[5][N];

int colmin = N, colmax = 0;

void init(int R, int C, int sr, int sc, int M, char *S)
{
	int x = sr, y = sc;

	col = C;

	string s;

	block[x][y] = 1;

	for(int i = 0; i < M; i++) s.push_back(S[i]);

	for(int i = 0; i < s.size(); i++)
	{
		block[x][y] = 1;

		int id = dxy(s[i]);

		if(id == -1) break;

		x = x + dx[id], y = y + dy[id];

		block[x][y] = 1;

		//cout<<"BLOCK "<<s.size()<<" "<<x<<" "<<y<<"\n";
	}

	for(int i = 1; i <= 2; i++)
		for(int j = 1; j <= C; j++)
			pref[i][j] = pref[i][j - 1] + block[i][j];

	for(int i = 1; i <= 2; i++)
	{
		for(int j = 1; j <= C; j++)
		{
			if(block[i][j]) pref[i][j] = pref[i][j - 1];

			else pref[i][j] = 1 + pref[i][j - 1];
		}
	}

	for(int i = 1; i <= 2; i++)
	{
		for(int j = 1; j <= C; j++)
		{
			int st = j, entrou = 0;

			while(!block[i][j] and j <= C) j++, entrou = 1;

			if(entrou) j--;

			if(!block[i][st])
			{
				zeros.push_back({st, j});

				ans[i][st] ++;

				inicio[i][st] = 1;

				//cout<<"ADD "<<i<<", "<<st<<"\n";

				//ans[i][j] --;
			}
		}
	}

	for(int i = 1; i <= 2; i++)
		for(int j = 1; j <= col; j++) ans[i][j] += ans[i][j - 1];

	for(int i = 1; i <= 2; i++)
	{
		for(int j = 1; j <= C; j++)
		{
			if(block[i][j] == 1)
			{
				colmax = max(colmax, j);

				colmin = min(colmin, j);
			}
		}
	}
}

int colour(int ar, int ac, int br, int bc)
{
    int cnt = 0;

    if(ar == br)
    {
    	if(!block[ar][ac - 1] and ac > 1 and !block[ar][ac ]) return 1 + ans[ar][bc] - ans[ar][ac - 1];

    	else return ans[ar][bc] - ans[ar][ac - 1];
    }

    else
    {
    	int dA = 0, dB = 0;

    	if(block[1][colmin] and block[2][colmin] and ac < colmin) dA ++;

    	if(block[1][colmax] and block[2][colmax] and bc > colmax) dB ++;

    	//cout<<"DELTA "<<dA<<" "<<dB<<'\n';

    	ac = max(ac, colmin);

    	bc = min(bc, colmax);

    	if(!block[1][ac - 1] and ac > 1 and !block[1][ac ]) dA += 1 + ans[1][bc] - ans[1][ac - 1];

    	else dA += ans[1][bc] - ans[1][ac - 1];

    //	cout<<"DELTA LINHA 1 "<<colmin<<" "<<colmax<<" "<<dA<<"\n";

       	if(!block[2][ac - 1] and ac > 1 and !block[2][ac ]) dA += 1 + ans[2][bc] - ans[2][ac - 1];

    	else dA += ans[2][bc] - ans[2][ac - 1];

     ///  	cout<<"DELTA LINHA 2 "<<colmin<<" "<<colmax<<" "<<dA<<"\n";


    	return dA + dB;
    }
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++)
                 ~~^~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:143:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 0;
         ^~~

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