Submission #46211

#	Time	Username	Problem	Language	Result	Execution time	Memory
46211		arman_ferdous	Three Friends (BOI14_friends)	C++11	0 / 100	578 ms	68168 KiB

friends

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

typedef long long ll;
const int N = 2000010;
int n;
string s;
ll h[N][2], p[N][2], b[2] = {101,103}, mod[2] = {916969619,998244353};

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

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/2;

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

	pair<ll,ll> h1, h2, part;
	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);

		if(l1 <= i && i <= r1) {
			int len = r1 - i;
			h1 = get(i+1,r1);
			part = get(l1,i-1);
			part.first = (part.first * p[len][0]) % mod[0];
			part.second = (part.second * p[len][1]) % mod[1];
			h1.first = (h1.first + part.first >= mod[0] ? h1.first + part.first - mod[0] : h1.first + part.first);
			h1.second = (h1.second + part.second >= mod[1] ? h1.second + part.second - mod[1] : h1.second + part.second);
		}
		else h1 = get(l1,r1);

		int l2 = (r1 + 1 == i ? r1 + 2 : r1 + 1);
		int r2 = (i > l2 ? l2 + len : l2 + len - 1);
		
		if(l2 <= i && i <= r2) {
			int len = r2 - i;
			h2 = get(i+1,r2);
			part = get(l2,i-1);
			part.first = (part.first * p[len][0]) % mod[0];
			part.second = (part.second * p[len][1]) % mod[1];
			h2.first = (h2.first + part.first >= mod[0] ? h2.first + part.first - mod[0] : h2.first + part.first);
			h2.second = (h2.second + part.second >= mod[1] ? h2.second + part.second - mod[1] : h2.second + part.second);
		}
		else h2 = get(l2,r2);

		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