Submission #1085930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085930		Sunbae	Three Friends (BOI14_friends)	C++17	35 / 100	1020 ms	68920 KiB

friends

#include <bits/stdc++.h>
#define z exit(0)
typedef long long ll;
using namespace std;
const int N = 2000002;
//
const int M = 1;
//
const ll mod[M] = {(ll)1e9+7}, p[M] = {31};
ll qs[M][N], P[M][N], INV[M][N];
ll c(char ch){ return ch - 'A' + 1;}
int L[N], R[N];
ll sum(int j, int l, int r){
	if(l > r) return 0;
	return ( qs[j][r] - ((l) ? qs[j][l-1] : 0) + mod[j] ) % mod[j];
}
ll powr(int j, ll A, ll B){
	A %= mod[j];
	ll res = 1;
	while(B){
		if(B&1) res = (res * A) % mod[j];
		A = (A * A) % mod[j];
		B >>= 1;
	}
	return res % mod[j];
}
string s;
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m = 0; cin>>n>>s;
	if(!(n&1)){ puts("NOT POSSIBLE"); return 0;}
	for(int j = 0; j<M; ++j){
		for(int i = 0; i<n; ++i){
			P[j][i] = (!i)? 1 : ((P[j][i-1] * p[j]) % mod[j]);
			qs[j][i] = (((i)? qs[j][i-1] : 0)  + (c(s[i]) * P[j][i]) % mod[j] ) % mod[j];
		}
		INV[j][n-1] = powr(j, P[j][n-1], mod[j]-2);
		for(int i = n-2; i>=0; --i) INV[j][i] = (INV[j][i+1] * p[j] )  % mod[j]; 
	}
	int sz = (n-1)/2;
	for(int i = 0; i<n; ++i){
		if(sz-1 < i){
			int cnt = 0;
			for(int j = 0; j<M; ++j){
				if(qs[j][sz-1] == ((sum(j, sz, i-1) * INV[j][sz]) % mod[j] + (sum(j, i+1, n-1) * INV[j][sz+1]) % mod[j]) % mod[j]) ++cnt;
			}
			if(cnt == M){ L[m] = 0; R[m++] = sz-1;}
		}else{
			int cnt = 0;
			for(int j = 0; j<M; ++j){
				if((sum(j, n-sz, n-1) * INV[j][n-sz]) % mod[j] == (sum(j, 0, i-1) + (sum(j, i+1, n-sz-1) * INV[j][1]) % mod[j] )  % mod[j] ) ++cnt;
			}
			if(cnt == M){ L[m] = n-sz; R[m++] = n-1; }
		}
	}
	if(!m){
		puts("NOT POSSIBLE");
	}else if(m > 1){
		set<string> st;
		bool ch = true;
		for(int i = 0; i<m; ++i){
			string tmp = s.substr(L[i], R[i]-L[i]+1);
			if(st.empty()) st.insert(tmp); 
			else if(st.find(tmp) == st.end()){ ch = false; break;}
		}
		if(ch){
			cout<<*st.begin(); 
		}else{
			cout<<"NOT UNIQUE";
		}
	}else{
		cout<<s.substr(L[0], R[0]-L[0]+1);
	}
}

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