oj.uz

Submission #622333

# Submission time Handle Problem Language Result Execution time Memory
622333 2022-08-04T07:23:16 Z patrikpavic2 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 267 ms 55568 KB 
/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  rainbow
* score: 12.0
* date:  2019-07-10 11:35:58.592760
*/
#include "rainbow.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
 
#define PB push_back
#define X first
#define Y second
 
using namespace std;
 
typedef pair < int, int > pt;
 
const int px[4] = {1, -1, 0, 0};
const int py[4] = {0, 0, 1, -1};
 
const int OFF = (1 << 18);
const int N = 2e5 + 500;
 
map < pt, bool > ima, ima2;
int toc = 0;
int LO, HI, I;
 
struct per_tour{
	int pref[10][N];
	void add(vector < pt > &v){
		for(pt x : v) pref[x.X][x.Y]++;
		for(int i = 0;i < 10;i++){
			int cur = 0;
			for(int j = 0;j < N;j++){
				cur += pref[i][j];
				pref[i][j] = cur;
				if(i) pref[i][j] += pref[i - 1][j];
			}
		}
	}
	int get2d(int x1,int x2,int y1,int y2){
		if(x1 > x2 || y1 > y2) return 0;
		return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
	}
};
 
per_tour deg[2], ob, ob2;
 
void init(int R, int C, int sr, int sc, int M, char *S) {
	int cx = sr, cy = sc;
	vector < pt > dod_deg0, dod_deg1, dod_ob, dod_ob2;
	ima[{cx, cy}] = 1;
	for(int i = 0;i < M;i++){
		if(S[i] == 'N') cx--;
		if(S[i] == 'S') cx++;
		if(S[i] == 'W') cy--;
		if(S[i] == 'E') cy++;
		ima[{cx, cy}] = 1;
	}
	for(pair < pt, bool > A : ima){
		pt x = A.X; //printf("POLJE %d %d\n", x.X, x.Y);
		dod_ob.PB({x.X, x.Y});
		ima2[{x.X, x.Y}] = 1;
		ima2[{x.X + 1, x.Y}] = 1;
		ima2[{x.X, x.Y + 1}] = 1;
		ima2[{x.X + 1, x.Y + 1}] = 1;
	}
	toc = (int)ima2.size();
	for(pair < pt, bool > A : ima2){
		pt x = A.X; //printf("TOCKA %d %d\n", x.X, x.Y);
		dod_ob2.PB({x.X, x.Y});
		if(ima2.count({x.X + 1, x.Y}) && (ima.count({x.X, x.Y}) || ima.count({x.X, x.Y - 1})))
			dod_deg0.PB({x.X, x.Y});
		if(ima2.count({x.X, x.Y + 1}) && (ima.count({x.X - 1, x.Y}) || ima.count({x.X, x.Y})))
			dod_deg1.PB({x.X, x.Y});
	}
	deg[0].add(dod_deg0);
	deg[1].add(dod_deg1);
	ob.add(dod_ob);
	ob2.add(dod_ob2);
}
 
int colour(int x1, int y1, int x2, int y2) {
	x2++, y2++;
	int E = 0;
	E += deg[0].get2d(x1    , x2 - 1, y1 + 1, y2 - 1);	
	E += deg[1].get2d(x1 + 1, x2 - 1, y1    , y2 - 1);	
	E += 2 * (x2 - x1 + y2 - y1);
	int kol = ob2.get2d(x1 + 1, x2 - 1, y1 + 1, y2 - 1); 
	int V = kol + 2 * (x2 - x1 + y2 - y1);
	//printf("V = %d E = %d\n", V, E);
	int F = E - V + 2;
	if(kol == toc) F++;
	F--; F -= ob.get2d(x1, x2 - 1, y1, y2 - 1);	
	return F;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 16396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31640 KB Output is correct
2 Correct 26 ms 31592 KB Output is correct
3 Correct 176 ms 45900 KB Output is correct
4 Correct 261 ms 55568 KB Output is correct
5 Correct 236 ms 55304 KB Output is correct
6 Correct 212 ms 49816 KB Output is correct
7 Correct 243 ms 49544 KB Output is correct
8 Correct 89 ms 32384 KB Output is correct
9 Correct 244 ms 55516 KB Output is correct
10 Correct 250 ms 55284 KB Output is correct
11 Correct 267 ms 49796 KB Output is correct
12 Correct 225 ms 53948 KB Output is correct
13 Correct 232 ms 55508 KB Output is correct
14 Correct 235 ms 55284 KB Output is correct
15 Correct 193 ms 49788 KB Output is correct
16 Correct 201 ms 48952 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31672 KB Output is correct
2 Runtime error 204 ms 48492 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 16396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 16396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -