Submission #584481

#	Time	Username	Problem	Language	Result	Execution time	Memory
584481		anubhavdhar	Three Friends (BOI14_friends)	C++11	100 / 100	74 ms	51472 KiB

friends

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;

const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 2e6 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;

const ll MOD1 = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1400305337;

const ll p1 = 29;
const ll p2 = 31;
const ll p3 = 37;

ll P[4][MAXN + 1];

#define make_hash(a, b, c) make_pair(a, make_pair(b, c))
typedef pair<ll, pair<ll, ll>> hash_type;

hash_type hash_val(string S){
	ll h1 = 0, h2 = 0, h3 = 0;
	for(char c : S){
		h1 = (h1 * p1 + (c - 'A' + 1)) % MOD1;
		h2 = (h2 * p2 + (c - 'A' + 1)) % MOD2;
		h3 = (h3 * p3 + (c - 'A' + 1)) % MOD3;
	}
	return make_hash(h1, h2, h3);
}

int N;
string S;
hash_type pref, suf;

bool check_pref(){
	
	ll h1 = suf.ff;
	ll h2 = suf.ss.ff;
	ll h3 = suf.ss.ss;

	for(int i = N / 2, v = N / 2 - 1; i < N - 1; ++i, --v){
		h1 = (h1 + (S[i] - S[i + 1]) * P[1][v] % MOD1 + MOD1) % MOD1;
		h2 = (h2 + (S[i] - S[i + 1]) * P[2][v] % MOD2 + MOD2) % MOD2;
		h3 = (h3 + (S[i] - S[i + 1]) * P[3][v] % MOD3 + MOD3) % MOD3;
		if(make_hash(h1, h2, h3) == pref){
			return true;
		}
	}
	return false;
}

bool check_suf(){
	
	ll h1 = pref.ff;
	ll h2 = pref.ss.ff;
	ll h3 = pref.ss.ss;

	for(int i = N / 2, v = 0; i; --i, ++v){
		h1 = (h1 + (S[i] - S[i - 1]) * P[1][v] % MOD1 + MOD1) % MOD1;
		h2 = (h2 + (S[i] - S[i - 1]) * P[2][v] % MOD2 + MOD2) % MOD2;
		h3 = (h3 + (S[i] - S[i - 1]) * P[3][v] % MOD3 + MOD3) % MOD3;
		if(make_hash(h1, h2, h3) == suf){
			return true;
		}
	}
	return false;
}

signed main(){

	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	P[1][0] = P[2][0] = P[3][0] = 1;
	F0Re(i, MAXN){
		P[1][i] = P[1][i - 1] * p1 % MOD1;
		P[2][i] = P[2][i - 1] * p2 % MOD2;
		P[3][i] = P[3][i - 1] * p3 % MOD3;
	}

	cin >> N >> S;
	if((N & 1) ^ 1){
		cout << "NOT POSSIBLE\n";
		exit(0);
	}

	pref = hash_val(S.substr(0, N / 2));
	suf = hash_val(S.substr(N / 2 + 1, N / 2));
	if(pref == suf){
		cout << S.substr(N / 2 + 1, N / 2) << '\n';
		exit(0);
	}

	bool t1 = check_pref();
	bool t2 = check_suf();

	if(t1 ^ t2){
		cout << (t1 ? S.substr(0, N / 2) : S.substr(N / 2 + 1, N / 2)) << '\n';
	}else{
		cout << "NOT " << (t1 ? "UNIQUE\n" : "POSSIBLE\n");
	}

	return 0;
}

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