Submission #308935

#	Time	Username	Problem	Language	Result	Execution time	Memory
308935		CaroLinda	Three Friends (BOI14_friends)	C++14	100 / 100	83 ms	8632 KiB

friends

#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()

using namespace std ;

int n ;
vector< string > possibleAnswers ;

void compare( vector<char> &part1, vector<char> &part2 )
{

	int t = sz(part1) ;
	if( sz(part2) != t+1 ) return ;

	vector<bool> preffix(t+1,false) , suffix(t+1,false) ;

	for(int i = 0 ; i < t ; i++ )
	{
		if( part1[i] != part2[i] ) break ;
		preffix[i] = true ;
	}

	for(int i = t ; i > 0 ; i-- )
	{
		if(part1[i-1] != part2[i]) break ;
		suffix[i] = true ;
	}

	for(int i = 0 ; i < t+1 ; i++ )
	{
		bool ok = true ;
		
		if(i) ok &= preffix[i-1] ;
		if(i < t) ok &= suffix[i+1] ;

		if(!ok) continue ;

		string str ;
		for(auto e : part1 ) str.push_back(e) ;
		possibleAnswers.pb(str) ;
		return ;

	}

}

void printAnswer(string str)
{
	cout << str << endl ;
	exit(0) ;
}

int main()
{
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;

	cin >> n ;
	vector<char> str(n) ;
	lp(i,0,n) cin >> str[i] ;

	if(n%2 == 0) printAnswer("NOT POSSIBLE") ;

	vector<char> part1, part2 ;
	int t = (n-1)/2 ;

	lp(i,0,t) part1.push_back(str[i]) ;
	lp(i,t,n) part2.push_back(str[i]) ;

	compare(part1, part2) ;

	part1.clear() ;
	part2.clear() ;

	lp(i,0,t+1) part2.push_back(str[i]) ;
	lp(i,t+1,n) part1.push_back(str[i]) ;

	compare(part1, part2) ;

	sort(all(possibleAnswers)) ;
	possibleAnswers.erase( unique(all(possibleAnswers)) , possibleAnswers.end() ) ;

	if(sz(possibleAnswers) == 0) printAnswer("NOT POSSIBLE") ;
	if(sz(possibleAnswers) == 1) printAnswer(possibleAnswers[0]) ;
	printAnswer("NOT UNIQUE") ;

}

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