Submission #852277

#	Time	Username	Problem	Language	Result	Execution time	Memory
852277		NK_	Three Friends (BOI14_friends)	C++17	0 / 100	28 ms	22780 KiB

friends

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;
	string S; cin >> S;

	vi F(26); for(auto& c : S) F[c-'a']++;

	if (N % 2 == 0) {
		cout << "NOT POSSIBLE" << nl;
		exit(0-0);
	}

	int M = (N - 1) / 2;

	vi OUT(N), IN(N);
	// IN[i] = A[i] == A[i + M + 1];
	// OUT[i] = A[i] == A[i + M] 


	for(int i = 0; i < N; i++) {
		if (i+M+1 < N) IN[i] = (S[i] == S[i+M+1]);
		if (i+M < N) OUT[i] = (S[i] == S[i+M]);
	}

	string ans1, ans2;

	// START WITH IN THEN SWITCH TO OUT
	{
		bool aft = 0;
		for(int i = 0; i < N; i++) {
			if (sz(ans1) == M) break;
			if (aft) {
				if (OUT[i]) ans1 += S[i];
				else break;
			} else {
				if (IN[i]) ans1 += S[i];
				else aft = 1;
			}		
		}
	}

	// START WITH OUT THEN SWITCH TO IN

	{ 
		bool aft = 0;
		for(int i = 0; i < N; i++) {
			if (sz(ans2) == M) break;
			if (aft) {
				if (IN[i]) ans2 += S[i];
				else break;
			} else {
				if (OUT[i]) ans2 += S[i];
				else aft = 1;
			}		
		}
	}	

	if (ans1 == ans2) ans2 = "";

	if (sz(ans1) == M && sz(ans2) == M) cout << "NOT UNIQUE" << nl;
	else if (sz(ans1) == M) cout << ans1 << nl; 
	else if (sz(ans2) == M) cout << ans2 << nl;
	else cout << "NOT POSSIBLE" << nl;

	exit(0-0);
} 

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