Comentário NOIC - OBI Fase 2 P1/P2 - Retângulo

retangulo.cpp

// Comentário NOIC - OBI Fase 2 P1/P2 - Retângulo
// Complexidade: O(N log N)
// Escrito por Lúcio Figueiredo

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+10;

int L[maxn];
ll P[maxn]; // soma de prefixo
int D[maxn];

ll S(int i, int j)
{
	return P[j] - P[i];
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &L[i]);

		P[i] = P[i-1] + 1ll*L[i]; // calculamos as somas de prefixo
	}

	for (int i = 1; i <= n; i++)
	{
		// busca binária para encontrar D[i]

		int ini = i+1, fim = n, ans = -1;

		while (ini <= fim)
		{
			int mid = (ini+fim)>>1;

			if (2*S(i, mid) == S(0, n)) // se é um diâmetro
			{
				ans = mid;
				break;
			}

			if (S(i, mid) > S(0, n)/2) fim = mid-1;
			else ini = mid+1;

		}

		D[i] = ans;
	}

	// quantidade de pontos com D[i] != -1
	int qtd = 0;
	for (int i = 1; i <= n; i++)
		if (D[i] != -1)
			qtd++;

	if (qtd >= 2) printf("S\n");
	else printf("N\n");
}