제출 #74548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74548		SpeedOfMagic	보물 찾기 (CEOI13_treasure2)	C++17	80 / 100	9 ms	1932 KiB

treasure

#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
/*
20
00000000000000000001
00000000000000000001
00000001000000000001
00000001000000000001
00000001000001000001
00000000000000000001
00000000000000000001
00111000000000000001
00111000000000000001
00111000000000000001
00000000000000000001
00000000001100000001
00000000000000000001
00000100000000000001
00000000000000000001
00000000000111000001
00000000000000000001
11111111111111111111
00000000000000000001
00000000000000000001
*/

int n;
/**
01
23
**/
int quarter(int r, int c) { return (r > n / 2) * 2 + (c > n / 2); }

vector<pair<int, int>> neighbours(int r, int c) {
	int q = quarter(r, c);
	if (q == 0)
		return {{r+1, c}, {r, c+1}, {r+1, c+1}};
	else if (q == 1)
		return {{r+1, c}, {r, c-1}, {r+1, c-1}};
	else if (q == 2)
		return {{r-1, c}, {r, c+1}, {r-1, c+1}};
	else
		return {{r-1, c}, {r, c-1}, {r-1, c-1}};
}

map<vector<int>, int> mem;
int get(int r1, int c1, int r2, int c2) {
	if (mem.count({r1, c1, r2, c2}))
		return mem[{r1, c1, r2, c2}];
	int res = countTreasure(r1, c1, r2, c2);
	mem[{r1, c1, r2, c2}] = res;
	return res;
}
	
void findTreasure (int N) {
	n = N;
	
	int pref[4][n + 1][n + 1];
	memset(pref, 0, sizeof(pref));
	char marked[4][n + 1][n + 1];
	memset(marked, 0, sizeof(marked));
	
	rep(z, 0, 4)
		rep(i, 1, n + 1)
			rep(j, 1, n + 1)
				if (quarter(i, j) == z) {
					for (pair<int, int> k : neighbours(i, j))
						if (quarter(k.first, k.second) != z && !marked[z][k.first][k.second]) {
							if (z == 0)
								pref[z][k.first][k.second] = get(k.first, k.second, n, n);
							else if (z == 1)
								pref[z][k.first][k.second] = get(k.first, 1, n, k.second);
							else if (z == 2)
								pref[z][k.first][k.second] = get(1, k.second, k.first, n);
							else
								pref[z][k.first][k.second] = get(1, 1, k.first, k.second);
							marked[z][k.first][k.second] = 1;
						}
			
					if (quarter(i, j) == 0)
						pref[z][i][j] = get(i, j, n, n);
					else if (quarter(i, j) == 1)
						pref[z][i][j] = get(i, 1, n, j);
					else if (quarter(i, j) == 2)
						pref[z][i][j] = get(1, j, i, n);
					else
						pref[z][i][j] = get(1, 1, i, j);
				}
	
	int ans[n + 1][n + 1];	
	rep(i, 1, n + 1)
        rep(j, 1, n + 1) {
			int z = quarter(i, j);
			if (z == 0)
				ans[i][j] = pref[z][i][j] - pref[z][i + 1][j] - pref[z][i][j + 1] + pref[z][i + 1][j + 1];
			else if (z == 1) 
				ans[i][j] = pref[z][i][j] - pref[z][i + 1][j] - pref[z][i][j - 1] + pref[z][i + 1][j - 1];
			else if (z == 2)
				ans[i][j] = pref[z][i][j] - pref[z][i - 1][j] - pref[z][i][j + 1] + pref[z][i - 1][j + 1];
			else
				ans[i][j] = pref[z][i][j] - pref[z][i - 1][j] - pref[z][i][j - 1] + pref[z][i - 1][j - 1];
		}
	
	rep(i, 1, n + 1)
		rep(j, 1, n + 1)
			if (ans[i][j])
				Report(i, j);

	/*
	ooxxoo
	ooxxoo
	xxxxxx
	xxxxxx
	ooxxoo
	ooxxoo
	
	ooxoo
	ooxoo
	xxxxx
	ooxoo
	ooxoo
	*/
}

• Subtask 1: 80 / 100