Submission #62927

#	Time	Username	Problem	Language	Result	Execution time	Memory
62927		MatheusLealV	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	68 / 100	4 ms	748 KiB

treasure

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

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

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, A;

		int rnd = rand()%2;

		if(rnd == 0) A = countTreasure(l, id, mid, id);

		else A = countTreasure(mid + 1, id, r, id);

		solve2(id, l, mid, (!rnd ? A : k - A)  ), solve2(id, mid + 1, r, (rnd ? A : k - A));
	}
}

void findTreasure (int N)
{
	n = N;

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

	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]) Report(i, j);
		}
	//	cout<<"COLUNA "<<i<<" = "<<col[i]<<"\n";
	}
}

• Subtask 1: 68 / 100