Submission #105634

#	Time	Username	Problem	Language	Result	Execution time	Memory
105634		sams	Three Friends (BOI14_friends)	C++17	0 / 100	197 ms	4348 KiB

friends

#include <bits/stdc++.h>

using namespace std;

int n;
string u;
map<char, int> ct;
int main()
{
	cin >> n >> u;

	if(n % 2 == 0)
	{
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	
	for(int i = 0 ; i < n ; ++i)
	{
		ct[u[i]]++;
	}
	int ii = 0;
	char rep = '.';
	for(auto it: ct)
	{
		if(it.second%2 == 1) ii++, rep = it.first;
	}

	if(ii > 1)
	{
		cout << "NOT POSSIBLE\n";
		return 0;
	}

	if(ct[rep] == 1)
	{
		u.erase(u.find(rep), u.find(rep)-1);
		//cout << rep << "\n";
		n--;
		n /= 2;
		//cout << u << "\n\n";
		for(int i = 0, j = n ; i < n ; i++, j++)
		{	
			//cout << i << " " << j << "\n";
			if(u[i] != u[j])
			{	
				//cout << "oi\n";
				cout << "NOT POSSIBLE\n";
				return 0;
			}
		}
		for(int i = 0 ; i < n ; i++) cout << u[i];
		cout << "\n";
	}else{

		int bb = 1, ee = 1, mm1 = 1, mm2 = 1, mm3 = 1 , p2 = -1, p3 = -1;

		if(u[0] == rep)
		{	
			n++;
			n /= 2;
			for(int i = 1, j = n ; i < n ; ++i, j++)
			{
				if(u[i] != u[j])
				{
					bb = 0;
					break;
				}
			}
			n *= 2;
			n--;
		}else bb = 0;

		if(u[n - 1] == rep)
		{	
			n--;
			n /= 2;
			for(int i = 0, j = n ; i < n ; ++i, j++)
			{
				if(u[i] != u[j])
				{
					ee = 0;
					break;
				}
			}
			n *= 2;
			n++;
		}else ee = 0;

		if(bb + ee > 1)
		{
			cout << "NOT UNIQUE\n";
			return 0;
		}

		if(u[n/2] == rep)
		{
			n--;
			n /= 2;

			for(int  i = 0, j = n+1 ; i < n ; ++i, ++j)
			{
				if(u[i] != u[j])
				{
					mm1 = 0;
					break;
				}
			}
			n *= 2;
			n++;
		}

		if(mm1 + bb + ee > 1)
		{
			cout << "NOT UNIQUE\n";
			return 0;
		}
		
		bool ok = false;
		
		n--;
		n /= 2;

		for(int  i = 0, j = n ; i < n ; ++i, ++j)
		{
			if(u[i] != u[j])
			{
				if(ok == false && u[j+1] == u[i]) ok = true, p2 = j, j++;
				else
				{
					mm2 = 0;
					break;
				}
			}
		}

		n *= 2;
		n++;

		if(mm2 + mm1 + bb + ee > 1)
		{
			cout << "NOT UNIQUE\n";
			return 0;
		}

		ok = true;
		int mid = (n+1)/2;
		for(int  i = 0, j = mid ; i < mid ; ++i, ++j)
		{
			if(u[i] != u[j])
			{
				if(ok == false && u[i+1] == u[j]) ok = true, p3 = i, i++;
				else
				{
					mm3 = 0;
					break;
				}
			}
		}
		if(mm3 + mm2 + mm1 + bb + ee > 1)
		{
			cout << "NOT UNIQUE\n";
			return 0;
		}

		if(bb == 1)
		{	
			n++;
			n /= 2;

			for(int  i = 1 ; i < n ; ++i) cout << u[i];
		}else if(ee == 1 || mm1 == 1 || mm2)
		{
			n--;
			n /= 2;
			for(int  i = 0 ; i < n ; ++i) cout << u[i];
		}else if(mm3 == 1)
		{
			n++;
			n /= 2;
			for(int  i = 0 ; i < n ; ++i)
				if(i != p3) 
					cout << u[i];
		}
		cout << "\n";
	}

	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:56:51: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
   int bb = 1, ee = 1, mm1 = 1, mm2 = 1, mm3 = 1 , p2 = -1, p3 = -1;
                                                   ^~

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