제출 #575220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575220		thiago_bastos	세 명의 친구들 (BOI14_friends)	C++17	100 / 100	20 ms	8184 KiB

friends

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

bool subseq(string& a, string& b) {
	int n = size(a);

	vector<bool> pre(n + 1);
	bool suf = true;

	pre[0] = true;
	for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] && a[i - 1] == b[i - 1];

	if(pre.back()) return true;

	for(int i = n - 1; i >= 0; --i) {
		suf = suf && a[i] == b[i + 1];
		if(pre[i] && suf) return true;
	}

	return suf;
}

void solve() {

	string s;
	int n;

	cin >> n >> s;
	
	if(~n & 1) {
		cout << "NOT POSSIBLE\n";	
		return;
	}

	string a = s.substr(0, n / 2) + s.substr(0, n / 2);
	string b = s.substr(n / 2 + 1) + s.substr(n / 2 + 1);

	if(subseq(a, s)) {
		if(a == b || !subseq(b, s)) cout << s.substr(0, n / 2) << '\n';
		else cout << "NOT UNIQUE\n";
	} else if(subseq(b, s)) cout << s.substr(n / 2 + 1) << '\n';
	else cout << "NOT POSSIBLE\n";
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
//	cin >> t;
	while(t--) solve();
	return 0;
}

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