Submission #95978

#	Time	Username	Problem	Language	Result	Execution time	Memory
95978		luciocf	Three Friends (BOI14_friends)	C++14	0 / 100	5 ms	1016 KiB

friends

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 2e5+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