Submission #1085925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085925		Sunbae	Three Friends (BOI14_friends)	C++17	35 / 100	201 ms	262144 KiB

friends

#include <bits/stdc++.h>
#define z exit(0)
typedef long long ll;
using namespace std;
const int N = 2000002;
const ll mod[2] = {(ll)1e9+7, (ll)1e9+7}, p[2] = {31, 37};
char s[N];
ll qs[2][N], P[2][N], INV[2][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 V[N];
signed main(){
	int n, m = 0; scanf("%d %s", &n, s);	
	string ss;
	for(int i = 0; i<n; ++i) ss += s[i];
	if(!(n&1)){ puts("NOT POSSIBLE"); return 0;}
	for(int j = 0; j<2; ++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<2; ++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 == 2){ L[m] = 0; R[m++] = sz-1;}
		}else{
			int cnt = 0;
			for(int j = 0; j<2; ++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 == 2){ L[m] = n-sz; R[m++] = n-1; }
		}
	}
	if(!m){
		puts("NOT POSSIBLE");
	}else if(m > 1){
		int k = 0;
		for(int i = 0; i<m; ++i) V[k++] = ss.substr(L[i], R[i]-L[i]+1); 
		sort(V, V+k); k = unique(V, V+k) - V;
		if(k == 1){
			for(int i = L[0]; i<=R[0]; ++i) printf("%c", s[i]); 
		}else{
			puts("NOT UNIQUE");
		}
	}else{
		for(int i = L[0]; i<=R[0]; ++i) printf("%c", s[i]); 
	}
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:27:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  int n, m = 0; scanf("%d %s", &n, s);
      |                ~~~~~^~~~~~~~~~~~~~~~

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