Submission #46214

#	Time	Username	Problem	Language	Result	Execution time	Memory
46214		arman_ferdous	Three Friends (BOI14_friends)	C++11	0 / 100	18 ms	6580 KiB

friends

#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;
}

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