제출 #1085934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085934		Sunbae	세 명의 친구들 (BOI14_friends)	C++17	100 / 100	83 ms	60888 KiB

friends

//not pass just because of my stupid implementation
//use too many arrays!
#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, R, hsh[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, h = qs[0][sz-1];
			for(int j = 0; j<M; ++j){
				if(h == ((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){ hsh[m++] = h; L = 0; R = sz-1;} 
		}else{
			int cnt = 0, h = (sum(0, n-sz, n-1) * INV[0][n-sz]) % mod[0];
			for(int j = 0; j<M; ++j){
				if(h == (sum(j, 0, i-1) + (sum(j, i+1, n-sz-1) * INV[j][1]) % mod[j] )  % mod[j] ) ++cnt;
			}
			if(cnt == M){ hsh[m++] = h; L = n-sz; R = n-1;}
		}
	}	
	sort(hsh, hsh+m); m = unique(hsh, hsh+m) - hsh;
	if(!m){
		cout<<"NOT POSSIBLE";
	}else if(m > 1){
		cout<<"NOT UNIQUE";
	}else{
		cout<<s.substr(L, R-L+1);
	}
}

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