Submission #163289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
163289	2019-11-12T11:52:00 Z	rolypolyvg295	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	100 / 100	8 ms	888 KB

treasure

#include "treasure.h"
#include <vector>
#include <map>
#include <utility>
#include <tuple>
using namespace std;

int n;
map<int, int> mp;
vector<int> line_total;
vector<vector<int>> grid_total;

int rect_to_hash(int y1, int x1, int y2, int x2){
	int ret = y1-1;
	ret *= n;
	ret += x1-1;
	ret *= n;
	ret += y2-1;
	ret *= n;
	ret += x2-1;

	return ret;
}

tuple<int, int, int, int> hash_to_rect(int hash){
	int x2 = (hash % n) + 1;
	hash /= n;
	int y2 = (hash % n) + 1;
	hash /= n;
	int x1 = (hash % n) + 1;
	hash /= n;
	int y1 = (hash % n) + 1;

	return make_tuple(y1, x1, y2, x2);
}

int get(int y1, int x1, int y2, int x2){
	int hash = rect_to_hash(y1, x1, y2, x2);
	if (mp.find(hash) == mp.end())
		mp[hash] = countTreasure(y1, x1, y2, x2);

	return mp[hash];
}

int getRectEnd(int endY, int startX){
	if (endY == 0)
		return 0;

	if (n - endY > endY)
		return get(1, startX, n, n) - get(endY+1, startX, n, n);
	else
		return get(1, startX, endY, n);
}

int getRectStart(int endY, int endX){
	if (endY == 0)
		return 0;

	if (n - endY > endY)
		return get(1, 1, n, endX) - get(endY+1, 1, n, endX);
	else
		return get(1, 1, endY, endX);
}

int getLine(int y){
	return line_total[y] - line_total[y-1];
}

void calLine(){
	line_total.assign(n+1, 0);
	for (int i = 1; i <= n; i++){
		line_total[i] = getRectEnd(i, 1);
	}
}

int getGrid(int y, int x){
	return grid_total[y][x] - grid_total[y][x-1];
}

void calGrid(){
	grid_total.assign(n+1, vector<int>(n+1, 0));

	for (int i = 1; i <= n; i++){
		int left = 1;
		int right = n-1;
		while (right){
			if (right > left){
				grid_total[i][left] = getLine(i) - (getRectEnd(i, left+1) - getRectEnd(i-1, left+1));
			}else{
				grid_total[i][left] = getRectStart(i, left) - getRectStart(i-1, left);
			}

			left++;
			right--;
		}

		grid_total[i][left] = getLine(i);
	}
}

void findTreasure (int N) {
	n = N;
	mp.clear();

	calLine();
	calGrid();

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (getGrid(i, j))
				Report(i, j);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct - N = 5, K = 289, score = 10
2	Correct	2 ms	376 KB	Output is correct - N = 10, K = 4475, score = 10
3	Correct	2 ms	376 KB	Output is correct - N = 15, K = 22289, score = 10
4	Correct	2 ms	376 KB	Output is correct - N = 16, K = 28928, score = 10
5	Correct	4 ms	504 KB	Output is correct - N = 55, K = 4005289, score = 10
6	Correct	5 ms	504 KB	Output is correct - N = 66, K = 8305803, score = 10
7	Correct	5 ms	632 KB	Output is correct - N = 77, K = 15383161, score = 10
8	Correct	7 ms	760 KB	Output is correct - N = 88, K = 26244416, score = 10
9	Correct	8 ms	888 KB	Output is correct - N = 99, K = 42032201, score = 10
10	Correct	8 ms	888 KB	Output is correct - N = 100, K = 43760000, score = 10