Submission #403055

#	Time	Username	Problem	Language	Result	Execution time	Memory
403055		BERNARB01	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	166 ms	4488 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1002;
const int maxN = (int) 2e5 + 9;

int sub = 1;

int a[N][N], vis[N][N], done[N][N], u, l, d, r, sum1[maxN], sum2[maxN], sum12[maxN], vis2[2][N];

array<int, 4> di = {0, 0, 1, -1};
array<int, 4> dj = {1, -1, 0, 0};


bool valid(int i, int j) {
	return (u <= i && i <= d && l <= j && j <= r && !vis[i][j] && !done[i][j]);
}

void dfs(int i, int j) {
	done[i][j] = 1;
	for (int k = 0; k < 4; k++) {
		int ni = i + di[k];
		int nj = j + dj[k];
		if (valid(ni, nj)) {
			dfs(ni, nj);
		}
	}
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	if (R == 2) {
		sub = 2;
	}
	u = 1; d = R;
	l = 1; r = C;
	vis[sr][sc] = 1;
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') {
			sr--;
		} else if (S[i] == 'S') {
			sr++;
		} else if (S[i] == 'E') {
			sc++;
		} else {
			sc--;
		}
		if (sub == 2) {
			vis2[sr][sc] = 1;
		} else {
			vis[sr][sc] = 1;
		}
	}
	if (sub == 2) {
		for (int i = 1; i <= C; i++) {
			sum1[i] = sum1[i - 1] + vis2[1][i];
			sum2[i] = sum2[i - 1] + vis2[2][i];
			sum12[i] = sum1[i] + sum2[i];
		}
	}
}

int colour(int ar, int ac, int br, int bc) {
	u = ar; d = br;
	l = ac; r = bc;
	int ans = 0;
	if (sub == 2) {
		int len = (r - l + 1);
		if (u == d) {
			if (d == 1) {
				return len - (sum1[r] - sum1[l - 1]);
			} else {
				return len - (sum2[r] - sum2[l - 1]);
			}
		} else {
			return (2 * len - (sum12[r] - sum12[l - 1]));
		}
	}
	for (int i = u; i <= d; i++) {
		for (int j = l; j <= r; j++) {
			if (!vis[i][j] && !done[i][j]) {
				dfs(i, j);
				ans++;
			}
		}
	}
	memset(done, 0, sizeof done);
	return ans;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:58:34: warning: array subscript 2 is above array bounds of 'int [2][1002]' [-Warray-bounds]
   58 |    sum2[i] = sum2[i - 1] + vis2[2][i];
      |                            ~~~~~~^
rainbow.cpp:11:86: note: while referencing 'vis2'
   11 | int a[N][N], vis[N][N], done[N][N], u, l, d, r, sum1[maxN], sum2[maxN], sum12[maxN], vis2[2][N];
      |                                                                                      ^~~~

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