Submission #46209

#	Time	Username	Problem	Language	Result	Execution time	Memory
46209		arman_ferdous	Three Friends (BOI14_friends)	C++11	0 / 100	432 ms	45916 KiB

friends

#include <bits/stdc++.h>
using namespace std;

#define addmod(a,b,m) (a + b >= m ? a + b - m : a + b)

typedef long long ll;
const int N = 2000010;
int n;
string s;
ll h[N], p[N], base = 103, mod = 998244353;

ll get(int l, int r) {
	l++, r++;
	if(r < l) return 0;
	return (h[r] - (p[r-l+1] * h[l-1] % mod) + mod) % mod;
}

int main() {
	cin >> n >> s;
	if(~n&1) { cout << "NOT POSSIBLE\n"; return 0; }
	int len = n/2;

	h[0] = 0, p[0] = 1;
	for(int i = 0; i < n; i++) {
		h[i+1] = (h[i]*base + s[i] - 'A' + 1) % mod;
		p[i+1] = p[i] * base % mod;
	}

	int idx = -1, cnt = 0;
	for(int i = 0; i < n; i++) {
		int l1 = (i == 0 ? 1 : 0);
		int r1 = (l1 < i && i <= l1 + len - 1 ? l1 + len : l1 + len - 1);
		ll h1 = get(l1,r1);

		int l2 = (r1 + 1 == i ? r1 + 2 : r1 + 1);
		int r2 = (i > l2 ? l2 + len : l2 + len - 1);
		ll h2 = get(l2,r2);

		if(l1 <= i && i <= r1) {
			int len = r1 - i;
			h1 = get(i+1,r1);
			ll part = get(l1,i-1) * p[len] % mod;
			h1 = addmod(h1,part,mod);
		}
		else if(l2 <= i && i <= r2) {
			int len = r2 - i;
			h2 = get(i+1,r2);
			ll part = get(l2,i-1) * p[len] % mod;
			h2 = addmod(h2,part,mod);
		}
		if(h1 == h2) cnt++, idx = i;
	}
	if(idx == -1) cout << "NOT POSSIBLE\n";
	else if(cnt > 1) cout << "NOT UNIQUE\n";
	else {
		string ans = "";
		int now = 0;
		for(int i = 0; i < n && now < len; i++) {
			if(i == idx) continue;
			ans += s[i];
			now++;
		}
		cout << ans << "\n";
	}
	return 0;
}

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