Submission #69084

#TimeUsernameProblemLanguageResultExecution timeMemory
69084MatheusLealVThree Friends (BOI14_friends)C++17
100 / 100
43 ms27460 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]);

	// Checar se a resposta é "A"

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

	//cout<<A<<" "<<B<<"\n";

	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]});

	//cout<<a<<" "<<b<<" "<<B[t]<<" "<<dif<<"\n";

	// CHECAR SE "C" É RESPOSTA

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

	//cout<<C<<" "<<D<<"\n";

	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";

	//cout<<c<<" "<<d<<" "<<D[t2]<<" "<<dif2<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...