oj.uz

Submission #40587

# Submission time Handle Problem Language Result Execution time Memory
40587 2018-02-05T07:43:29 Z pica4500 Treasure (different grader from official contest) (CEOI13_treasure2) C++
0 / 100
 1000 ms 604 KB 
#include "treasure.h"
#include<iostream>
using namespace std;

int ptr = 0;
bool treasure[105][105];

int tot = 0;
int cur = 0;

bool chk(int r1, int c1, int r2, int c2) {
	if (r2 < r1 || c2 < c1) return false;
	return true;
}

int sum(int r1, int c1, int r2, int c2) {
	return ((r2 - r1 + 1) * (c2 - c1 + 1));
}

int solve(int r1, int c1, int r2, int c2) {
	if ((cur == tot) || !chk(r1, c1, r2, c2)) return 0;

	int midR = (r1 + r2) / 2;
	int midC = (c1 + c2) / 2;

	int LUr1 = r1;
	int LUc1 = c1;
	int LUr2 = midR;
	int LUc2 = midC;

	int LDr1 = midR + 1;
	int LDc1 = c1;
	int LDr2 = r2;
	int LDc2 = midC;

	int RUr1 = r1;
	int RUc1 = midC + 1;
	int RUr2 = midR;
	int RUc2 = c2;

	int RDr1 = midR + 1;
	int RDc1 = midC + 1;
	int RDr2 = r2;
	int RDc2 = c2;

	int LU = 0;
	int LD = 0;
	int RU = 0;
	int RD = 0;

	int LUD = 0;
	int RUD = 0;

	int curAdd = 0;

	int all = countTreasure(r1, c1, r2, c2);
	if (all == sum(r1, c1, r2, c2)) {
		for (int i = r1; i <= r2; i++) {
			for (int j = c1; j <= c2; j++) {
				treasure[i][j] = true;
			}
		}
		cur += all;
		curAdd += all;
		return curAdd;
	}

	//2개 계산
	if (chk(r1, c1, r2, midC)) {
		if (cur == tot) return curAdd;
		LUD = countTreasure(r1, c1, r2, midC);
		if (LUD == sum(r1, c1, r2, midC)) {
			for (int i = r1; i <= r2; i++) {
				for (int j = c1; j <= midC; j++) {
					treasure[i][j] = true;
				}
			}
			cur += LUD;
			curAdd += LUD;
			if (curAdd == all) return curAdd;
			goto MID;
		}
		else if ((curAdd + LUD) == all) {
			curAdd += solve(r1, c1, r2, midC);
			return curAdd;
		}
		else if (LUD == 0) goto MID;
	}

	if (chk(LUr1, LUc1, LUr2, LUc2)) {
		if (cur == tot) return curAdd;
		LU = countTreasure(LUr1, LUc1, LUr2, LUc2);
		if (LU == sum(LUr1, LUc1, LUr2, LUc2)) {
			for (int i = LUr1; i <= LUr2; i++) {
				for (int j = LUc1; j <= LUc2; j++) {
					treasure[i][j] = true;
				}
			}
			cur += LU;
			curAdd += LU;
			if (curAdd == all) return curAdd;
		}
		else {
			if (LU) {
				curAdd += solve(LUr1, LUc1, LUr2, LUc2);
				if (curAdd == all) return curAdd;
			}
		}
	}
	if (chk(LDr1, LDc1, LDr2, LDc2)) {
		if (cur == tot) return curAdd;
		LD = LUD - LU;
		if (LD == sum(LDr1, LDc1, LDr2, LDc2)) {
			for (int i = LDr1; i <= LDr2; i++) {
				for (int j = LDc1; j <= LDc2; j++) {
					treasure[i][j] = true;
				}
			}
			cur += LD;
			curAdd += LD;
			if (curAdd == all) return curAdd;
		}
		else {
			if (LD) {
				curAdd += solve(LDr1, LDc1, LDr2, LDc2);
				if (curAdd == all) return curAdd;
			}
		}
	}
MID:
	if (chk(r1, midC + 1, r2, c2)) {
		if (cur == tot) return curAdd;
		RUD = all - LUD;
		if (RUD == sum(r1, midC + 1, r2, c2)) {
			for (int i = r1; i <= r2; i++) {
				for (int j = midC + 1; j <= c2; j++) {
					treasure[i][j] = true;
				}
			}
			cur += RUD;
			curAdd += RUD;
			return curAdd;
		}
		else if ((curAdd + RUD) == all) {
			curAdd += solve(r1, midC + 1, r2, c2);
			return curAdd;
		}
		else if (RUD == 0) return curAdd;
	}

	if (chk(RUr1, RUc1, RUr2, RUc2)) {
		if (cur == tot) return curAdd;
		RU = countTreasure(RUr1, RUc1, RUr2, RUc2);
		if (RU == sum(RUr1, RUc1, RUr2, RUc2)) {
			for (int i = RUr1; i <= RUr2; i++) {
				for (int j = RUc1; j <= RUc2; j++) {
					treasure[i][j] = true;
				}
			}
			cur += RU;
			curAdd += RU;
			if (curAdd == all) return curAdd;
		}
		else {
			if (RU) {
				curAdd += solve(RUr1, RUc1, RUr2, RUc2);
				if (curAdd == all) return curAdd;
			}
		}
	}
	if (chk(RDr1, RDc1, RDr2, RDc2)) {
		if (cur == tot) return curAdd;
		RD = RUD - RU;
		if (RD == sum(RDr1, RDc1, RDr2, RDc2)) {
			for (int i = RDr1; i <= RDr2; i++) {
				for (int j = RDc1; j <= RDc2; j++) {
					treasure[i][j] = true;
				}
			}
			cur += RD;
			curAdd += RD;
			if (curAdd == all) return curAdd;
		}
		else {
			if (RD) {
				curAdd += solve(RDr1, RDc1, RDr2, RDc2);
				if (curAdd == all) return curAdd;
			}
		}
	}
}

void findTreasure (int N) {
    tot = countTreasure(1, 1, N, N);
	if (tot == 0) return;

	solve(1, 1, N, N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (treasure[i][j]) {
				Report(i, j);
			}
		}
	}
}

Compilation message

grader.c: In function 'int main()':
grader.c:63:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         my_assert(strlen(A[i]+1) == N, "each line of the map must contain N zeroes or ones (before loop)");
                                  ^
treasure.cpp: In function 'int solve(int, int, int, int)':
treasure.cpp:191:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 248 KB Time limit exceeded
2 Execution timed out 1079 ms 352 KB Time limit exceeded
3 Execution timed out 1072 ms 568 KB Time limit exceeded
4 Execution timed out 1076 ms 568 KB Time limit exceeded
5 Execution timed out 1068 ms 568 KB Time limit exceeded
6 Execution timed out 1078 ms 568 KB Time limit exceeded
7 Execution timed out 1079 ms 568 KB Time limit exceeded
8 Execution timed out 1078 ms 604 KB Time limit exceeded
9 Execution timed out 1080 ms 604 KB Time limit exceeded
10 Execution timed out 1072 ms 604 KB Time limit exceeded