제출 #62929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62929		MatheusLealV	보물 찾기 (CEOI13_treasure2)	C++17	72 / 100	22 ms	668 KiB

treasure

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

int ans[150][150], col[150], n, pref[150];

void solve(int l, int r, int k)
{
	if(!k) return;

	if(l == r) col[l] = k;

	else
	{
		int mid = (l + r)/2;

		int A = countTreasure(1, l, n, mid);

		solve(l, mid, A), solve(mid + 1, r, k - A);
	}
}

void solve2(int id, int l, int r, int k)
{
	if(!k) return;

	if(k == r - l + 1)
	{
		for(int i = l; i <= r; i++) ans[i][id] = 1;

		return;
	}

	if(l == r) ans[l][id] = k;

	else
	{
		int mid = (l + r)/2;

		int A = countTreasure(1, 1, mid, id);

		for(int i = 1; i <= id; i++)
			for(int j = 1; j <= mid; j++)
				A -= ans[j][i];

		solve2(id, l, mid, A), solve2(id, mid + 1, r, k - A);
	}
}

int query[150][150];

void findTreasure (int N)
{
	n = N;

	solve(1, N, countTreasure(1, 1, N, N));

	for(int i = 1; i <= N; i++) pref[i] = pref[i - 1] + col[i];

	for(int i = 1; i <= N; i++) solve2(i, 1, N, col[i]);

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

• Subtask 1: 72 / 100