제출 #274830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274830		arnold518	보물 찾기 (CEOI13_treasure2)	C++14	40 / 100	14 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 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;
 
	int p=(N+1)/2;
	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>=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<=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-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<=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=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++) if(ans[i][j]) Report(i, j);
}

• Subtask 1: 40 / 100