oj.uz

Submission #57353

# Submission time Handle Problem Language Result Execution time Memory
57353 2018-07-14T15:40:36 Z MatheusLealV Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 195 ms 6364 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 616 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 124 ms 5080 KB Output is correct
4 Correct 131 ms 6248 KB Output is correct
5 Correct 101 ms 6248 KB Output is correct
6 Correct 107 ms 6248 KB Output is correct
7 Correct 92 ms 6248 KB Output is correct
8 Correct 121 ms 6248 KB Output is correct
9 Correct 101 ms 6324 KB Output is correct
10 Correct 103 ms 6324 KB Output is correct
11 Correct 195 ms 6324 KB Output is correct
12 Correct 108 ms 6324 KB Output is correct
13 Correct 85 ms 6364 KB Output is correct
14 Correct 83 ms 6364 KB Output is correct
15 Correct 99 ms 6364 KB Output is correct
16 Correct 111 ms 6364 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6364 KB Output is correct
2 Runtime error 5 ms 6364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -