Submission #62931

#	Time	Username	Problem	Language	Result	Execution time	Memory
62931		MatheusLealV	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	72 / 100	18 ms	648 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(n*(r - l + 1) == k)
	{
		for(int i = l; i <= r; i++) col[i] = n;

		return;
	}

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

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

		int A = countTreasure(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 = countTreasure(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);
	}
}

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

	//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