답안 #57314 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57314	2018-07-14T14:24:10 Z	fredbr	무지개나라 (APIO17_rainbow)	C++17	23 / 100	132 ms	43380 KB

rainbow

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

using namespace std;

const int maxn = 110;
const int maxm = 202020;
int r, c;
char riv[maxn][maxm];
char vis[maxn][maxm];
int pini[3][maxm], pfim[3][maxm];

int soma1 = 0, soma2 = 0;

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

void dfs(int x, int y, int x1, int y1, int x2, int y2)
{
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {

		int xx = x+dx[i];
		int yy = y+dy[i];
		if (xx < x1 or xx > x2 or yy < y1 or yy > y2) continue;
		if (riv[xx][yy] or vis[xx][yy]) continue;
		dfs(xx, yy, x1, y1, x2, y2);
	}
}

void init2()
{
	for (int i = 1; i <= c; i++) {

		if (!riv[1][i] and (i == 1 or riv[1][i-1]))
			pini[1][i]++;
		if (!riv[2][i] and (i == 1 or riv[2][i-1]))
			pini[2][i]++;
		if (!riv[1][i] and (i==c or riv[1][i+1]))
			pfim[1][i]++;
		if (!riv[2][i] and (i==c or riv[2][i+1]))
			pfim[2][i]++;

		if ((pini[1][i] and pini[2][i]) or
		    ((riv[1][i]^riv[2][i]) and (pini[1][i]|pini[2][i])))
			pini[0][i]++;

		if ((pfim[1][i] and pfim[2][i]) or
		    ((riv[1][i]^riv[2][i]) and (pfim[1][i]|pfim[2][i])))
		    pfim[0][i]++;

		pini[0][i] += pini[0][i-1];	
		pini[1][i] += pini[1][i-1];			
		pini[2][i] += pini[2][i-1];
		pfim[0][i] += pfim[0][i-1];
		pfim[1][i] += pfim[1][i-1];	
		pfim[2][i] += pfim[2][i-1];

	}
	// for (int i = 1; i <= c; i++)
	// 	cout << pini[1][i]-pini[1][i-1] << " ";
	// cout << "\n";
	// for (int i = 1; i <= c; i++)
	// 	cout << pini[2][i]-pini[2][i-1] << " ";
	// cout << "\n";
	// for (int i = 1; i <= c; i++)
	// 	cout << pini[0][i]-pini[0][i-1] << " ";
	// cout << "\n";
}

void init(int rr, int cc, int sr, int sc, int m, char* s)
{
	r = rr, c = cc;

	int x = sr, y = sc;
	riv[x][y] = 1;
	for (int i = 0; i < m; i++) {

		if (s[i] == 'N') x--;
		else if (s[i] == 'E') y++;
		else if (s[i] == 'S') x++;
		else y--;
		riv[x][y] = 1;
	}

	if (r == 2)
		init2();
}

int colour1(int x1, int y1, int x2, int y2)
{
	int ans = 0;

	for (int i = x1; i <= x2; i++)
		for (int j = y1; j <= y2; j++)
			vis[i][j] = 0;
	for (int i = x1; i <= x2; i++)
		for (int j = y1; j <= y2; j++)
			if (!riv[i][j] and !vis[i][j])
				dfs(i, j, x1, y1, x2, y2), ans++;

	return ans;
}

int colour2(int x1, int y1, int x2, int y2)
{
	if (x2 == 1) {

		int ans = pini[1][y2] - pfim[1][y1-1];
		return ans;
	}
	if (x1 == 2) {
		int ans = pini[2][y2] - pfim[2][y1-1];
		return ans;
	}
	return pini[0][y2]-pfim[0][y1-1];
}

int colour(int x1, int y1, int x2, int y2)
{
	if (r == 2 and c > 50)
		return colour2(x1, y1, x2, y2);
	else return colour1(x1, y1, x2, y2);
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	11 ms	1000 KB	Output is correct
3	Correct	28 ms	1364 KB	Output is correct
4	Correct	20 ms	1364 KB	Output is correct
5	Correct	10 ms	1364 KB	Output is correct
6	Correct	2 ms	1364 KB	Output is correct
7	Correct	2 ms	1364 KB	Output is correct
8	Correct	2 ms	1364 KB	Output is correct
9	Correct	3 ms	1364 KB	Output is correct
10	Correct	5 ms	1364 KB	Output is correct
11	Correct	26 ms	1364 KB	Output is correct
12	Correct	22 ms	1364 KB	Output is correct
13	Correct	13 ms	1364 KB	Output is correct
14	Correct	11 ms	1364 KB	Output is correct
15	Correct	3 ms	1364 KB	Output is correct
16	Correct	2 ms	1364 KB	Output is correct
17	Correct	3 ms	1364 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1364 KB	Output is correct
2	Correct	3 ms	1364 KB	Output is correct
3	Correct	93 ms	6188 KB	Output is correct
4	Correct	88 ms	9276 KB	Output is correct
5	Correct	132 ms	12028 KB	Output is correct
6	Correct	104 ms	14980 KB	Output is correct
7	Correct	108 ms	17788 KB	Output is correct
8	Correct	131 ms	20580 KB	Output is correct
9	Correct	111 ms	23568 KB	Output is correct
10	Correct	106 ms	26440 KB	Output is correct
11	Correct	112 ms	29304 KB	Output is correct
12	Correct	85 ms	32172 KB	Output is correct
13	Correct	110 ms	35000 KB	Output is correct
14	Correct	72 ms	37836 KB	Output is correct
15	Correct	106 ms	40544 KB	Output is correct
16	Correct	101 ms	43380 KB	Output is correct

Subtask #3
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1364 KB	Output is correct
2	Runtime error	4 ms	43380 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	11 ms	1000 KB	Output is correct
3	Correct	28 ms	1364 KB	Output is correct
4	Correct	20 ms	1364 KB	Output is correct
5	Correct	10 ms	1364 KB	Output is correct
6	Correct	2 ms	1364 KB	Output is correct
7	Correct	2 ms	1364 KB	Output is correct
8	Correct	2 ms	1364 KB	Output is correct
9	Correct	3 ms	1364 KB	Output is correct
10	Correct	5 ms	1364 KB	Output is correct
11	Correct	26 ms	1364 KB	Output is correct
12	Correct	22 ms	1364 KB	Output is correct
13	Correct	13 ms	1364 KB	Output is correct
14	Correct	11 ms	1364 KB	Output is correct
15	Correct	3 ms	1364 KB	Output is correct
16	Correct	2 ms	1364 KB	Output is correct
17	Correct	3 ms	1364 KB	Output is correct
18	Runtime error	4 ms	43380 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	11 ms	1000 KB	Output is correct
3	Correct	28 ms	1364 KB	Output is correct
4	Correct	20 ms	1364 KB	Output is correct
5	Correct	10 ms	1364 KB	Output is correct
6	Correct	2 ms	1364 KB	Output is correct
7	Correct	2 ms	1364 KB	Output is correct
8	Correct	2 ms	1364 KB	Output is correct
9	Correct	3 ms	1364 KB	Output is correct
10	Correct	5 ms	1364 KB	Output is correct
11	Correct	26 ms	1364 KB	Output is correct
12	Correct	22 ms	1364 KB	Output is correct
13	Correct	13 ms	1364 KB	Output is correct
14	Correct	11 ms	1364 KB	Output is correct
15	Correct	3 ms	1364 KB	Output is correct
16	Correct	2 ms	1364 KB	Output is correct
17	Correct	3 ms	1364 KB	Output is correct
18	Runtime error	4 ms	43380 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Halted	0 ms	0 KB	-

답안 #57314

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 24.0

Subtask #4 0 / 27.0

Subtask #5 0 / 26.0

Subtask #1
11.0 / 11.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 24.0

Subtask #4
0 / 27.0

Subtask #5
0 / 26.0