Submission #95981

#TimeUsernameProblemLanguageResultExecution timeMemory
95981luciocfThree Friends (BOI14_friends)C++14
0 / 100
90 ms5372 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 2e6+10;
 
int n;
 
char num[maxn], a[maxn], b[maxn];

int get_pref(void)
{
	int ind = 0;
	for (int i = 1; i <= n/2; i++)
	{
		if (a[i] != b[i]) break;
		ind = i;
	}

	return ind;
}

int get_suf(void)
{
	int ind = (n+1)/2+1;
	for (int i = (n+1)/2; i >= 2; i--)
	{
		if (a[i] != b[i-1]) break;
		ind = i;
	}

	return ind;
}
 
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 = get_pref(), suf = get_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 = get_pref(), suf = get_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";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...