제출 #249549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249549		Kevin_Zhang_TW	보물 찾기 (CEOI13_treasure2)	C++17	0 / 100	1 ms	436 KiB

treasure

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 110;
#include "treasure.h"
bool res[maxn][maxn];
int n;
int query(pair<int,int> LD, pair<int,int> UR) {
	return countTreasure(LD.first, LD.second, UR.first, UR.second);
}
void reply() {
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= n;++j)
			if (res[i][j])
				Report(i, j);
}
int pf[maxn][maxn];
void good() {
	int all = query({1,1}, {n,n});
//if (n > 20) return;
	for (int i = 1;i <= n;++i) {
		for (int j = 1;j <= n;++j) {
			int a, b, c, d;
			//a = mcnt({1, 1}, {i-1, n}) ,
			a = pf[i-1][n];
			b = (i > n-i ? all - query({1, 1}, {i, n}) : query({i+1, 1}, {n, n}))  ;//,
			c = (j > n-j ? query({1, 1}, {n, j-1}) : all - query({1, j}, {n, n})) ;
			d = (j > n-j ? all - query({1, 1}, {n, j}) : query({1, j+1}, {n, n}));
			//int a = query({1, 1}, {i-1, n}),
			//b = query({i+1,1}, {n, n}),
			//c = query({1, 1}, {n, j-1}),
			//d = query({1, j+1}, {n, n});

			res[i][j] = all
				- a - b - c - d
				//+ mcnt({1,1}, {i-1,j-1})
				//+ mcnt({1,j+1}, {i-1, n})
				+ query({1, 1}, {i-1, j-1})
				+ query({1, j+1}, {i-1, n})
				+ query({i+1,1}, {n,j-1})
				+ query({i+1,j+1}, {n, n})
				;
			pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + res[i][j];
			//cout << i << ' ' << j << " : "  << res[i][j] << '\n';
		}
	}
}
void findTreasure (int n) {
	::n = n;
	good();
	reply();
}

• Subtask 1: 0 / 100