Submission #63139

#	Time	Username	Problem	Language	Result	Execution time	Memory
63139		shoemakerjo	Three Friends (BOI14_friends)	C++14	100 / 100	140 ms	55536 KiB

friends

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod = 1000000009;
const int p1 = 37;

ll modpow(int base, int p) {
	if (p == 0) return 1;\
	if (p & 2) {
		ll tmp = modpow(base, p/2);
		return (tmp*tmp)%mod;
	}
	ll tmp = modpow(base, p-1);
	return (tmp*base) % mod;
}

const int maxn = 2000010;
ll preh[maxn];
ll sufh[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	string u;
	cin >> N >> u;
	if (N%2 == 0) {
		cout << "NOT POSSIBLE" << endl;
		return 0;
	}
	vector<int> rem; //just push back stuff
	int le = (N-1)/2;

	ll fh = 0;
	ll sh = 0;

	for (int i = 0; i < le; i++) {
		fh = (fh*p1) + (u[i]-'A'+1);
		fh %= mod;
		preh[i] = fh;
	}

	set<int> sols;

	preh[le] = preh[le-1]*p1 + (u[le]-'A'+1);
	preh[le] %= mod;
	ll ofh = fh;

	for (int i = le+1; i < N; i++) {
		sh = (sh*p1) + (u[i]-'A'+1);
		sh %= mod;
	}

	if (fh == sh){

		rem.push_back(le);
		sols.insert(sh);
	}


	// cout << fh << " - " << sh << endl;

	ll cp = 1LL;
	//compute suffix hashes
	sufh[le] = u[le]-'A'+1;
	for (int i = le-1; i >= 0; i--) {
		cp = (cp*p1)%mod;
		sufh[i] = (sufh[i+1] + (cp*(u[i]-'A'+1)) )%mod;
	}
	// cout << u.substr(0, le+1) << endl;
	// for (int i = 0; i <= le; i++) {
	// 	cout << preh[i] << " " << sufh[i] << endl;
	// }
	cp = 1LL;
	for (int i = le-1; i >= 0; i--) {
		//consider meshing these together
		cp = (cp*p1)%mod;
		ll ch = 0LL;
		if (i > 0) {
			ch = (ch + preh[i-1]*cp)%mod;
		}
		ch = (ch + sufh[i+1])%mod;
		if (ch == sh) {
			rem.push_back(i);
			sols.insert(sh);
		}
		// cout << i << ": current hash: " << ch << endl;
	}



	//now do the second half of it 
	//recalculate prefix and suffix hashes
	//then we just go through and do exact same thing
	fill(preh, preh+maxn, 0);
	fill(sufh, sufh+maxn, 0);



	sh = ofh; //just flip b/c why not
	// cout << "new sh: " << sh << endl;

	preh[le] = u[le]-'A'+1;
	for (int i = le+1; i < N; i++) {
		preh[i] = ((preh[i-1]*p1) + u[i]-'A'+1)%mod;
	}

	sufh[N-1] = u[N-1]-'A'+1;
	cp = 1LL;
	for (int i = N-2; i >= 0; i--) {
		cp = (cp*p1)%mod;
		sufh[i] = (sufh[i+1] + (cp*(u[i]-'A'+1)) )%mod;
	}
	for (int i = N-1; i > le; i--) {
		//consider meshing these together
		cp = (cp*p1)%mod;
		if (i == N-1) cp = 1LL; 
		ll ch = 0LL;
		if (i > 0) {
			ch = (ch + preh[i-1]*cp)%mod;
		}
		if (i != N-1) ch = (ch + sufh[i+1])%mod;
		if (ch == sh) {
			rem.push_back(i);
			sols.insert(ch);
		}
		// cout << i << ": current hash: " << ch << endl;
	}
	///////
	///////
	///////

	if (rem.size() == 0) {
		cout << "NOT POSSIBLE" << endl;
		return 0;
	}
	if (sols.size() > 1) {
		cout << "NOT UNIQUE" << endl;
		return 0;
	}

	int ind = rem[0];

	string ans;
	if (ind < le) {
		ans = u.substr(le+1);
	}
	else {
		ans = u.substr(0, le);
	}
	cout << ans << endl;



}

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