oj.uz

Submission #274831

# Submission time Handle Problem Language Result Execution time Memory
274831 2020-08-19T16:27:15 Z arnold518 Treasure (different grader from official contest) (CEOI13_treasure2) C++14
100 / 100
 12 ms 1152 KB 
#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;
	}

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct - N = 5, K = 289, score = 10
2 Correct 1 ms 384 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 1 ms 384 KB Output is correct - N = 15, K = 22289, score = 10
4 Correct 1 ms 384 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 3 ms 512 KB Output is correct - N = 55, K = 4005289, score = 10
6 Correct 4 ms 640 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 5 ms 768 KB Output is correct - N = 77, K = 15383161, score = 10
8 Correct 7 ms 896 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 9 ms 1152 KB Output is correct - N = 99, K = 42032201, score = 10
10 Correct 12 ms 1024 KB Output is correct - N = 100, K = 43760000, score = 10