Submission #41196

#	Time	Username	Problem	Language	Result	Execution time	Memory
41196		IvanC	Three Friends (BOI14_friends)	C++14	100 / 100	211 ms	80276 KiB

friends

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MOD1 = 1e9 + 9;
const ll prime1 = 999983;
const ll invprime1 = 943912055;
const int MAXN = 2000011;
ll N,hash1[MAXN],pot1[MAXN],invpot1[MAXN];
vector<ll> possiveis;
set<ll> valores;
string S;
ll get_hash(ll a,ll b){
	if(a > b) return 0;
	ll val = hash1[b] - hash1[a-1];
	if(val < 0) val += MOD1;
	val *= invpot1[a-1];
	return val % MOD1;
}
void checa(int pos){
	if(pos == N/2 + 1){
		if(get_hash(1,pos-1) == get_hash(pos+1,N)){
			possiveis.push_back(pos-1);
			valores.insert(get_hash(1,pos-1));
		}
	}
	else if(pos <= N/2){
		int resta = pos - 1;
		ll val1 = get_hash(1,pos - 1);
		int falta = N/2 - resta;
		ll val2 = get_hash(pos + 1,pos + falta);
		ll val3 = (val1 + pot1[resta]*val2) % MOD1;
		ll val4 = get_hash(pos+falta+1,N);
		if(val3 == val4){
			possiveis.push_back(pos-1);
			valores.insert(val4);
		}
	} 
	else{
		int resta = N - pos;
		ll val1 = get_hash(pos+1,N);
		int falta = N/2 - resta;
		ll val2 = get_hash(pos - falta,pos-1);
		ll val3 = (val2 + pot1[falta]*val1) % MOD1;
		ll val4 = get_hash(1,pos - falta - 1);
		if(val3 == val4){
			possiveis.push_back(pos-1);
			valores.insert(val4);
		}
	}
}
int main(){
	cin >> N >> S;
	if(N == 2){
		if(S[0] == S[1]) cout << S[0] << endl;
		else cout << "NOT UNIQUE" << endl;
		return 0;
	}
	if(N % 2 != 1){
		cout << "NOT POSSIBLE" << endl;
		return 0;
	}
	pot1[0] = invpot1[0] = 1;
	for(int i = 1;i<=N;i++){
		invpot1[i] = (invpot1[i-1]*invprime1) % MOD1;
		pot1[i] = (pot1[i-1]*prime1) % MOD1;
		hash1[i] = (hash1[i-1] + pot1[i]*S[i-1]) % MOD1;
	}
	for(int i = 1;i<=N;i++) checa(i);
	if(valores.size() == 0){
		cout << "NOT POSSIBLE" << endl;
		return 0;
	}
	else if(valores.size() > 1){
		cout << "NOT UNIQUE" << endl;
		return 0;
	}
	else{
		S.erase(S.begin() + possiveis[0]);
		S.resize(N/2);
		cout << S << endl;
	}
	return  0;
}

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