제출 #46214

#제출 시각아이디문제언어결과실행 시간메모리
46214arman_ferdous세 명의 친구들 (BOI14_friends)C++11
0 / 100
18 ms6580 KiB
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

// check if [l1,r1] is equal to [l2,r2]
bool match(int l1, int r1, int l2, int r2) {
	while(l1 <= r1 && l2 <= r2) {
		if(s[l1] != s[l2])
			return false;
		l1++, l2++;
	} return true;
}

// search for [l2,r2] in [l1,r1] with exactly one mismatch and skip it
bool match_and_skip(int l1, int r1, int l2, int r2) {
	int cnt = 0;
	while(l1 <= r1 && l2 <= r2) {
		if(s[l1] != s[l2]) cnt++, l2--;
		if(cnt > 1) return false;
		l1++, l2++;
	} return cnt == 1;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> s;
	if(~n&1) { cout << "NOT POSSIBLE\n"; return 0; }
	int len = n>>1;

	int idx = -1, cnt = 0;
	if(match(1,len,len+1,len+len)) idx = 1, cnt++;					// x(...)(...)
	if(match(0,len-1,len+1,len+len)) idx = 0, cnt++;				// (...)x(...)
	if(match(0,len-1,len,len+len-1)) idx = 0, cnt++;				// (...)(...)x

	if(match_and_skip(0,len,len+1,len+len)) idx = len+1, cnt++;		// (.x..)(...)
	if(match_and_skip(0,len-1,len,len+len-1)) idx = 0, cnt++;		// (...)(.x..)

	if(idx == -1) cout << "NOT POSSIBLE\n";
	else if(cnt > 1) cout << "NOT UNIQUE\n";
	else {
		string ans = "";
		for(int i = 0; i < len; i++)
			ans += s[i+idx];
		cout << ans << "\n";
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...