Submission #906292

#	Time	Username	Problem	Language	Result	Execution time	Memory
906292		MongHwa	Three Friends (BOI14_friends)	C++17	100 / 100	12 ms	8192 KiB

friends

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

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