Submission #748444

#	Time	Username	Problem	Language	Result	Execution time	Memory
748444		mariowong	Three Friends (BOI14_friends)	C++14	35 / 100	1072 ms	8108 KiB

friends

#include <bits/stdc++.h>
using namespace std;
 
int n,pos1,pos2,ct,ans;
string s,t,r,anss;
bool ok;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> s;
	if (n%2 == 0){
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	for (int i=1;i<=n/2;i++) t+=s[i];
	for (int i=n/2+1;i<n;i++) r+=s[i];
	for (int i=0;i<n/2;i++){
		if (t[i] == r[i])
		ct++;
	}
	for (int i=0;i<n;i++){
		if (ct == n/2){
			ans++;
			if (ans > 1 && t != anss){
				ok=true;
				break;	
			} else if (ans == 1) anss=t;
		}
		if (pos1 != n/2){
			if (t[pos1] == r[pos1])
			ct--;
			t[pos1]=s[i];
			if (t[pos1] == r[pos1])
			ct++;
			pos1++;
		}
		else
		{
			if (t[pos2] == r[pos2])
			ct--;
			r[pos2]=s[i];
			if (t[pos2] == r[pos2])
			ct++;
			pos2++;
		}
	}
	if (ct == n/2){
		ans++;
		if (ans > 1 && t != anss) ok=true;
		else if (ans == 1) anss=t;
	}
	if (ok) cout << "NOT UNIQUE\n";
	else if (ans == 0) cout << "NOT POSSIBLE\n";
	else cout << anss << "\n";
	return 0;
}	

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