Submission #62932

#	Time	Username	Problem	Language	Result	Execution time	Memory
62932		MatheusLealV	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	72 / 100	26 ms	800 KiB

treasure

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

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

int save[102][102];

int query(int x, int y, int xi, int yi)
{
	if(save[xi][yi] != -1) return save[xi][yi];

	return save[xi][yi] = countTreasure(x, y, xi, yi);
}

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 = query(1, 1, n, mid);

		for(int i = 1; i < mid; i++) A -= col[i];

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

int qtd = 0;

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 = query(1, 1, mid, id);

		qtd ++;

		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);
	}
}

void findTreasure (int N)
{
	n = N;

	memset(save, -1, sizeof save);

	solve(1, N, query(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]);

	//cout<<"QUANTIDADE == "<<qtd<<"\n";

	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