Submission #115792

#	Time	Username	Problem	Language	Result	Execution time	Memory
115792		Mahdi_Jfri	Three Friends (BOI14_friends)	C++14	100 / 100	79 ms	21912 KiB

friends

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

#define ll long long
#define pb push_back

const int maxn = 2e6 + 20;
const int mod = 1e9 + 7;
const int base = 4001;

int pw[maxn] , h[maxn];

int get(int l , int r)
{
	if(l >= r)
		return 0;
	return (h[r] - (1LL * h[l] * pw[r - l] % mod) + mod) % mod;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	pw[0] = 1;
	for(int i = 1; i < maxn; i++)
		pw[i] = 1LL * pw[i - 1] * base % mod;

	int n;
	string s;
	cin >> n >> s;

	if(n % 2 == 0)
		return cout << "NOT POSSIBLE" << endl , 0;

	for(int i = 0; i < n; i++)
		h[i + 1] = (1LL * h[i] * base + s[i]) % mod;

	int ans = -1 , H = -1;
	for(int i = 0; i < n; i++)
	{
		int h1 , h2;
		if(i <= n / 2)
		{
			h1 = (1LL * get(0 , i) * pw[n / 2 - i] + get(i + 1 , n / 2 + 1)) % mod;
			h2 = get(n / 2 + 1 , n);
		}
		else
		{
			h1 = get(0 , n / 2);
			h2 = (1LL * get(n / 2 , i) * pw[n / 2 - (i - n / 2)] + get(i + 1 , n)) % mod;
		}

		if(h1 == h2)
		{
			if(ans != -1 && H != h1)
				return cout << "NOT UNIQUE" << endl , 0;
			ans = i;
			H = h1;
		}
	}

	if(ans == -1)
		return cout << "NOT POSSIBLE" << endl , 0;

	if(ans <= n / 2)
		cout << s.substr(n / 2 + 1 , n / 2) << endl;
	else
		cout << s.substr(0 , n / 2) << endl;
}

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