Submission #105689

#	Time	Username	Problem	Language	Result	Execution time	Memory
105689		thiago4532	Three Friends (BOI14_friends)	C++17	0 / 100	1079 ms	33728 KiB

friends

#include <bits/stdc++.h>
#define subs(a, b) substr(a, b-a+1)
#define hash _hash
#define int int64_t

using namespace std;
int p1 = 1e9 + 7, p2 = 1e9 + 9;

int hash(string str){
	long long num = 1;
	long long ans=0;
	for(int i=0;i<(int)str.size();i++){
		ans += (num * (int64_t)(str[i] - 'A' + 1))%p2;
		// cout << "POS " << i << ": " << (num * (int64_t)(str[i] - 'A' + 1)) << "\n";
		ans %= p2;
		num = (num * p1)%p2;
	}
	// cout << "VAL: " << num << "\n";
	return ans;
}

int pot(long long a, long long b, long long m){
	long long r = 1;
	while(b){
		if(b&1) r = (r * (a%m))%m;

		a = ((a%m) * (a%m))%m;
		b /= 2;
	}
	return r;
}
int pref[2000001], suff[2000001];

int32_t main() {
	int n;
	cin >> n;
	string str;
	cin >> str;
	
	pref[0] = (str[0] - 'A' + 1);
	long long aux = p1;
	for(int i=1;i<n;i++){
		pref[i] = (pref[i-1] + aux * (str[i] - 'A' + 1))%p2;
		aux = (aux*p1)%p2;
	}
	
	suff[n-1] = (str[n-1] - 'A' + 1);
	for(int i=n-2;i>=0;i--){
		suff[i] = ((str[i] - 'A' + 1) + (p1 * (long long)suff[i+1])%p2)%p2;
	}

	// cout << "HASH: " << hash(str) << "\n";
	// cout << (pref[2] + ((pot(p1, 3, p2) * (int64_t)suff[4]))%p2)%p2 << "\n";

	if(n%2 == 0){
		cout << "NOT POSSIBLE\n";
		return 0;
	}

	int resp = -1, val = 0;
 	int k = (n-1)/2;

	for(int i=0;i<n;i++){
		int h1 = 0, h2 = 0;
		if(i < k){
			if(i == 0) h1 = ((pref[k] - pref[0])*pot(p1, p2-2, p2) + p2)%p2;
			else h1 = ( pref[i-1] + ((pref[k] - pref[i])*pot(p1, (p2-2), p2))%p2 + p2) % p2;
			h2 = suff[k+1];
		}else{
			h1 = pref[k-1];
			h2 = ((pref[i-1] - pref[k-1]) + (suff[i+1] * pot(p1, (i-k), p2)%p2 + p2))%p2;
		}

		// cout << h1 << " " << h2 << "\n";

		if(h1 == h2){
			if(resp != -1 && resp != h1){
				cout << "NOT UNIQUE\n";
				return 0;
			}
			resp = h1;
			val = i;
		}
	}
	if(resp == -1){
		cout << "NOT POSSIBLE\n";
	}else{
		for(int i=0;i<n;i++)
			if(i != val) cout << str[i] << " ";
		cout << "\n";
	}
}
	

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