Submission #274826

#	Time	Username	Problem	Language	Result	Execution time	Memory
274826		arnold518	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	80 / 100	9 ms	1024 KiB

treasure

#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 100;

int N;

int p;
int ans[MAXN+10][MAXN+10];
map<pair<pii, pii>, int> M;

int query(int y1, int x1, int y2, int x2)
{
	if(y1>y2) swap(y1, y2);
	if(x1>x2) swap(x1, x2);
	if(M.find({{y1, x1}, {y2, x2}})!=M.end()) return M[{{y1, x1}, {y2, x2}}];
	return M[{{y1, x1}, {y2, x2}}]=countTreasure(y1, x1, y2, x2);
}

void findTreasure(int _N)
{
	N=_N;

	p=(N+1)/2;
	for(int i=p-1; i>=1; i--) for(int j=p-1; j>=1; j--) ans[i][j]=query(i, j, N, N)-query(i+1, j, N, N)-query(i, j+1, N, N)+query(i+1, j+1, N, N);
	for(int i=p+1; i<=N; i++) for(int j=p-1; j>=1; j--) ans[i][j]=query(i, j, 1, N)-query(i-1, j, 1, N)-query(i, j+1, 1, N)+query(i-1, j+1, 1, N);
	for(int i=p-1; i>=1; i--) for(int j=p+1; j<=N; j++) ans[i][j]=query(i, j, N, 1)-query(i+1, j, N, 1)-query(i, j-1, N, 1)+query(i+1, j-1, N, 1);

	for(int i=p-1; i>=1; i--)
	{
		int sum=0;
		for(int j=1; j<p; j++) sum+=ans[j][i];
		ans[p][i]=query(1, N, p, i)-query(1, N, p, i+1)-sum;	
	}
	for(int i=p-1; i>=1; i--)
	{
		int sum=0;
		for(int j=1; j<p; j++) sum+=ans[i][j];
		ans[i][p]=query(N, 1, i, p)-query(N, 1, i+1, p)-sum;
	}
	for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) M[{{p, p}, {N, N}}]+=ans[i][j];

	for(int i=p+1; i<=N; i++) for(int j=p+1; j<=N; j++) ans[i][j]=query(1, 1, i, j)-query(1, 1, i-1, j)-query(1, 1, i, j-1)+query(1, 1, i-1, j-1);

	for(int i=p+1; i<=N; i++)
	{
		int sum=0;
		for(int j=1; j<p; j++) sum+=ans[j][i];
		ans[p][i]=query(1, 1, p, i)-query(1, 1, p, i-1)-sum;
	}
	for(int i=p; i<=N; i++)
	{
		int sum=0;
		for(int j=1; j<p; j++) sum+=ans[i][j];
		ans[i][p]=query(1, 1, i, p)-query(1, 1, i-1, p)-sum;
	}
	

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

• Subtask 1: 80 / 100