Submission #906292

#TimeUsernameProblemLanguageResultExecution timeMemory
906292MongHwaThree Friends (BOI14_friends)C++17
100 / 100
12 ms8192 KiB
#include <iostream>
using namespace std;

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

	int n; string s;
	cin >> n >> s;

	if(n % 2 == 0)
		cout << "NOT POSSIBLE\n";
	else
	{
		string ans;
		string t1 = s.substr(1, n/2);
		string t2 = s.substr(1+n/2, n/2);

		int cnt = 0;
		for(int i = 0; i < n/2; i++)
			if(t1[i] != t2[i])
				cnt++;

		if(cnt == 0)
			ans = t1;

		for(int i = 0; i < n/2; i++)
		{
			int pre_cnt = cnt;
			if(t1[i] != t2[i])
				cnt--;
			t1[i] = s[i];
			if(t1[i] != t2[i])
				cnt++;

			if(cnt == 0 && pre_cnt > 0)
			{
				if(ans.empty())
					ans = t1;
				else
				{
					cout << "NOT UNIQUE\n";
					return 0;
				}
			}
		}

		for(int i = n/2; i < n; i++)
		{
			int pre_cnt = cnt;
			if(t1[i-n/2] != t2[i-n/2])
				cnt--;
			t2[i-n/2] = s[i];
			if(t1[i-n/2] != t2[i-n/2])
				cnt++;

			if(cnt == 0 && pre_cnt > 0)
			{
				if(ans.empty() || ans == t1)
					ans = t1;
				else
				{
					cout << "NOT UNIQUE\n";
					return 0;
				}
			}
		}

		if(!ans.empty())
			cout << ans << '\n';
		else
			cout << "NOT POSSIBLE\n";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...