Submission #925174

#	Time	Username	Problem	Language	Result	Execution time	Memory
925174		NintsiChkhaidze	Three Friends (BOI14_friends)	C++17	100 / 100	54 ms	40528 KiB

friends

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll
using namespace std;
 
const int N = 2e6 + 3,mod = 1e9 + 7;
 
int h[N],pwr[N],cnt[30];
 
signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
 
	pwr[0] = 1;
	for (int i = 1; i <= 2000001; i++)
		pwr[i] = (pwr[i - 1] * 31) % mod;
 
	int n;
	cin>>n;
 
	string s;
	cin>>s;
 
	s= '%'+s;
	for (int i = 1; i <= n; i++){
		h[i] = h[i - 1] + pwr[i] * (s[i] - 'A' + 1) % mod;
		h[i] %= mod;
		cnt[s[i] - 'A' + 1]++;
	}
 
	int id = 0;
	for (int i = 1; i <= 26; i++){
		if (cnt[i] % 2 == 1){
			if (id) {
				cout<<"NOT POSSIBLE"<<endl;
				exit(0);
			}
			id = i;
		}
	}
	
	if (!id) {
		cout<<"NOT POSSIBLE"<<endl;
		exit(0);
	}
 
	set <int> st;
	string ans = "";
 
	for (int i = 1; i <= n; i++){
		if (id != s[i] - 'A' + 1) continue;
 
		int hash1 = 0,hash2 = 0;
		int len = (n - 1)/2,p1=0,p2=0;
 
		if (len >= i){
			hash1 = h[i - 1] * 31 + (h[len + 1] - h[i]);
			hash1 %= mod; hash1 += mod; hash1 %= mod;
 
			hash2 = h[n] - h[len + 1]; hash2 += mod; hash2 %= mod;
			p2 = len+2; p1 = 2;
		}else{
			hash1 = h[len]; p1 = 1; p2 = len + 2;
			hash2 = (h[i - 1] - h[len]) * 31 + (h[n] - h[i]);
			hash2 %= mod; hash2 += mod; hash2 %= mod;	
		}
 
		int mx = max(p1,p2);
		hash1 *= pwr[mx-p1];
		hash2 *= pwr[mx-p2];
 
		if (hash1 % mod == hash2 % mod) {
			int sz=st.size();
			st.insert(hash1 % mod);
			if (st.size() > 1) {
				cout<<"NOT UNIQUE"<<endl;
				exit(0);
			}
			if (sz == 1) continue;
			
			if (len < i) {
				for (int j = 1; j <= len; j++)
					ans += s[j];
			}else{
				for (int j = n; j >= n - len + 1; j--){
					ans += s[j];
				}
				reverse(ans.begin(),ans.end());
			}
		}
	}
	
	if (st.size()) cout<<ans;
	else cout<<"NOT POSSIBLE"<<endl;
}

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