Submission #69085

#TimeUsernameProblemLanguageResultExecution timeMemory
69085MatheusLealVThree Friends (BOI14_friends)C++17
100 / 100
39 ms9516 KiB
#include <bits/stdc++.h>
#define N 2000050
using namespace std;

int n;

string s, A, B, C, D;

set< pair<string, char> > resp;

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

	cin>>n;

	cin>>s;

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

		return 0;
	}

	for(int i = 0; i < n/2; i++) A.push_back(s[i]);

	for(int i = n/2; i < n; i++) B.push_back(s[i]);

	for(int i = n/2 + 1; i < n; i++) C.push_back(s[i]);

	for(int i = 0; i < n/2 + 1; i++) D.push_back(s[i]);

	int a = (int)A.size() - 1, b = (int)B.size() - 1;

	int dif = 0, t = 0;

	while(a >= 0 and b >= 0)
	{
		if(A[a] != B[b])
		{
			t = b;

			dif ++;

			b --;
		}

		else a--, b--;
	}

	if(!dif) dif = 1;

	if(dif == 1) resp.insert({A, B[t]});

	int c = (int)C.size() - 1, d = (int)D.size() - 1;

	int dif2 = 0, t2 = 0;

	while(c >= 0 and d >= 0)
	{
		if(C[c] != D[d])
		{
			t2 = d;

			dif2 ++;

			d --;
		}

		else c--, d--;
	}

	if(!dif2) dif2 = 1;

	if(dif2 == 1) resp.insert({C, D[t2]});

	if(resp.size() == 0) cout<<"NOT POSSIBLE\n";

	else if(resp.size() == 1) cout<<(*resp.begin()).first<<"\n";

	else cout<<"NOT UNIQUE\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...