Submission #204821

#	Time	Username	Problem	Language	Result	Execution time	Memory
204821		MvC	Three Friends (BOI14_friends)	C++11	100 / 100	90 ms	9304 KiB

friends

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e6+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,tot;
string s1,s2,rs;
char c[nmax];
map<string,bool>mp;
void sol(string x,string y)
{
	if(x!=y)return;
	if(!mp[x])
	{
		mp[x]=1;
		tot++;
		rs=x;
	}
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>c[i];
	if(n%2==0)rc("NOT POSSIBLE");
	for(i=1;i<=n/2;i++)s1+=c[i];
	for(;i<n;i++)s2+=c[i];
	sol(s1,s2);
	s1=s2="";
	for(i=(n/2)+2;i<=n;i++)s1+=c[i];
	for(i=2;i<=(n/2)+1;i++)s2+=c[i];
	sol(s1,s2);
	s1=s2="";
	for(i=1;i<=n/2;i++)s1+=c[i];
	j=0;
	for(;i<=n;i++)if(c[i]==s1[j])j++;
	if(j==n/2)sol(s1,s1);
	s1="";
	for(i=(n/2)+2;i<=n;i++)s1+=c[i];
	j=0;
	for(i=1;i<=(n/2)+1;i++)if(c[i]==s1[j])j++;
	if(j==n/2)sol(s1,s1);
	if(!tot)cout<<"NOT POSSIBLE"<<endl;
	else if(tot>1)cout<<"NOT UNIQUE"<<endl;
	else cout<<rs<<endl;
	return 0;
}

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