Submission #95977

#	Time	Username	Problem	Language	Result	Execution time	Memory
95977		luciocf	Three Friends (BOI14_friends)	C++14	0 / 100	3 ms	760 KiB

friends

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n;

char num[maxn], a[maxn], b[maxn];

bool ok_pref(int pos)
{
	for (int i = 1; i <= pos; i++)
		if (a[i] != b[i])
			return false;

	return true;	
}

bool ok_suf(int pos)
{
	for (int i = (n+1)/2; i >= pos; i--)
		if (a[i] != b[i-1])
			return false;

	return true;
}

int busca_pref(void)
{
	int ini = 1, fim = n/2, ans = 0;

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

		if (ok_pref(mid)) ans = mid, ini = mid+1;
		else fim = mid-1;
	}

	return ans;
}

int busca_suf(void)
{
	int ini = 2, fim = (n+1)/2, ans = fim+1;

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

		if (ok_suf(mid)) ans = mid, fim = mid-1;
		else ini = mid+1;
	}

	return ans;
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> num[i];

	if (n%2==0)
	{
		cout << "NOT POSSIBLE\n";
		return 0;
	}

	int ans = 0, add = (n+1)/2, possible = -1;

	bool ok = 1;
	for (int i = 1; i < add; i++)
		if (num[i] != num[i+add]) ok = 0;

	if (ok) ans++, possible = add;

	for (int i = 1; i <= add; i++)
		a[i] = num[i];
	for (int i = add+1; i <= n; i++)
		b[i-add] = num[i];

	int pref = busca_pref(), suf = busca_suf();

	for (int i = 1; i < add; i++)
		if (pref >= i-1 && suf <= i+1) 
			ans++, possible = i;

	for (int i = add; i <= n; i++)
		a[i-add+1] = num[i];
	for (int i = 1; i < add; i++)
		b[i] = num[i];

	pref = busca_pref(), suf = busca_suf();

	for (int i = add+1; i <= n; i++)
		if (pref >= (i-add) && suf <= (i-add)+2)
			ans++, possible = i;

	if (!ans) cout << "NOT POSSIBLE\n";
	else if (ans > 1) cout << "NOT UNIQUE\n";
	else
	{
		for (int i = 1, ind = 1; i <= n && ind < add; i++)
			if (i != possible)
				cout << num[i], ind++;
		cout << "\n";
	}
}

• Subtask 1: 0 / 35
• Subtask 2: 0 / 65