Submission #232446

#	Time	Username	Problem	Language	Result	Execution time	Memory
232446		bysu	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	0 / 100	137 ms	262148 KiB

treasure

#include "treasure.h"

#include <iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;

int dp[101][101][101][101];

struct Pos {
	int r, c;
};

int limit = 0;
int halfLimit = 0;
vector<Pos> vec;

int isDpValue(int r1, int c1, int r2, int c2) {
	int& ret = dp[r1][c1][r2][c2];
	if (ret == -1) {
		ret = countTreasure(r1, c1, r2, c2);
	}
	if (ret == 0) {
		for (int i = r1; i <= r2; i++) {
			for (int j = c1; j <= c2; j++) {
				for (int k = i; k <= r2; k++) {
					for (int p = j; p <= c2; p++) {
						dp[i][j][k][p] = 0;
					}
				}
			}
		}
	}



	return ret;
}
int caseFunc(Pos start, Pos end) {
	int bigBox, underBox, upperBox, leftBox, rightBox, commonBox;

	if (dp[start.r][start.c][start.r][start.c] == 1)
		return 1;

	else {
		if (start.r < halfLimit) {
			// left up
			if (start.c < halfLimit) {
				bigBox = isDpValue(start.r, start.c, limit, limit);				// 1,1,2,2
				if (bigBox == 0) return 0;
				underBox = isDpValue(end.r + 1, start.c, limit, limit);	// 2,1,2,2
				rightBox = isDpValue(start.r, end.c + 1, limit, limit);	// 1,2,2,2

				if (underBox*rightBox == 0) commonBox = 0;
				else
					commonBox = isDpValue(end.r + 1, end.c + 1, limit, limit); // 2,2

				return bigBox - underBox - rightBox + commonBox;
			}
			// right up
			else {
				bigBox = isDpValue(start.r, 1, limit, start.c);
				if (bigBox == 0) return 0;

				underBox = isDpValue(end.r + 1, 1, limit, start.c);
				leftBox = isDpValue(start.r, 1, limit, start.c - 1);
				if (underBox *leftBox == 0) commonBox = 0;
				else
					commonBox = isDpValue(end.r + 1, 1, limit, start.c - 1);
				return bigBox - underBox - leftBox + commonBox;
			}
		}
		//left down
		else if (start.c < halfLimit) {
			bigBox = isDpValue(1, start.c, start.r, limit);
			if (bigBox == 0) return 0;

			upperBox = isDpValue(1, start.c, start.r - 1, limit);
			rightBox = isDpValue(1, end.c + 1, start.r, limit);
			commonBox = isDpValue(1, end.c + 1, start.r - 1, limit);

			return bigBox - upperBox - rightBox + commonBox;
		}
		// right down
		else {
			bigBox = isDpValue(1, 1, start.r, start.c);
			if (bigBox == 0) return 0;
			upperBox = isDpValue(1, 1, end.r - 1, start.c);
			leftBox = isDpValue(1, 1, start.r, end.c - 1);

			if (upperBox*leftBox == 0) commonBox = 0;
			else commonBox = isDpValue(1, 1, end.r - 1, end.c - 1);
			return bigBox - upperBox - leftBox + commonBox;
		}
	}
}


int devideFunc(int r1, int c1, int r2, int c2, int val) {
	Pos p, q;
	p.r = r1, p.c = c1;
	q.r = r2; q.c = c2;
	int ret = 0;
	if (val != -1)
		ret = val;
	else ret = caseFunc(p, q);

	if ((r2 - r1 + 1)*(c2 - c1 + 1) == ret)
		for (int i = r1; i <= r2; i++) {
			for (int j = c1; j <= c2; j++) {
				p.r = i, p.c = j;
				vec.push_back(p);
			}
		}

	else if (ret != 0) {

		int a = devideFunc(r1, c1, r2 / 2, c2 / 2, -1);
		int b = devideFunc(r1, c2 / 2 + 1, r2 / 2, c2, -1);
		int c = devideFunc(r2 / 2 + 1, c1, r2, c2 / 2, -1);
		int d = ret - a - b - c;
		devideFunc(r2 / 2 + 1, c2 / 2 + 1, r2, c2, d);
	}
	return ret;
}
void findTreasure(int N) {

	limit = N;
	if (N & 1)
		halfLimit = N / 2;
	else
		halfLimit = N / 2 + 1;

	memset(dp, -1, sizeof(dp));

	;
	devideFunc(1, 1, N, N, countTreasure(1, 1, N, N));


	for (int i = 0; i < vec.size(); i++)
		Report(vec[i].r, vec[i].c);
}

Compilation message (stderr)

treasure.cpp: In function 'void findTreasure(int)':
treasure.cpp:141:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++)
                  ~~^~~~~~~~~~~~

• Subtask 1: 0 / 100