Submission #1024419

#TimeUsernameProblemLanguageResultExecution timeMemory
1024419ByeWorldThree Friends (BOI14_friends)C++14
35 / 100
1016 ms33704 KiB
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e6+15;
const int INF = 2e18+10;
vector <int> mod = {1000000007, 1000001053};
vector <int> key = {29, 31};
int sum(int a, int b, int MOD){ return (a+b)%MOD; }
int mul(int a, int b, int MOD){ return (a*b)%MOD; }
int sub(int a, int b, int MOD){ return (a+MOD-b)%MOD; }
void chsum(int &a, int b, int MOD){ b%=MOD; a = (a+b)%MOD; }
void chmul(int &a, int b, int MOD){ b%=MOD; a = (a*b)%MOD; }
void chsub(int &a, int b, int MOD){ b %= MOD; a = (a+MOD-b)%MOD; }
int expo(int a, int b, int MOD){
	if(b==0) return 1;
	int te = expo(a, b/2, MOD); te = mul(te, te, MOD);
	return (b%2 ? mul(te, a, MOD) : te);
}

int n, ANS;
string s;
map <pii, int> m;
pii pr[MAXN];
int ex(int num, int len, int ty){ return expo(num, len, mod[ty]); }
int inv(int num, int len, int ty){ 
	return expo(expo(num, len, mod[ty]), mod[ty]-2, mod[ty]);}
pii GET(int x, int y){
	if(x>y) return pii(0,0);
	int len = y-x+1;
	int f = sub(pr[y].fi, mul(pr[x-1].fi, ex(key[0], len, 0), mod[0]), mod[0]);
	int s = sub(pr[y].se, mul(pr[x-1].se, ex(key[1], len, 1), mod[1]), mod[1]);
	return pii(f, s);
}

signed main(){
	cin >> n;
	cin >> s; s = '.'+s;
	if(n%2==0){ cout << "NOT POSSIBLE\n"; exit(0); }
	pr[0] = {0, 0};
	for(int i=1; i<=n; i++){
		pr[i].fi = sum(mul(pr[i-1].fi, key[0], mod[0]), (int)(s[i]-'A')+1, mod[0]);
		pr[i].se = sum(mul(pr[i-1].se, key[1], mod[1]), (int)(s[i]-'A')+1, mod[1]);
	}
	for(int i=1; i<=n; i++){
		pii x, y;
		if(i==(n+1)/2){ x = GET(1, n/2); y = GET((n+1)/2+1, n); }
		else if(i==1){ x = GET(2, n/2+1); y = GET(n/2+2, n); }
		else if(i==n){ x = GET(1, n/2); y = GET(n/2+1, n-1); }
		else if(i<(n+1)/2){
			y = GET((n+1)/2+1, n);
			x = GET(1, i-1); 
			int len = n/2-(i-1);
			x.fi = mul(x.fi, ex(key[0], len, 0), mod[0]);
			x.se = mul(x.se, ex(key[1], len, 1), mod[1]);
			pii te = GET(i+1, i+len);
			chsum(x.fi, te.fi, mod[0]); chsum(x.se, te.se, mod[1]);
		} else {
			y = GET(1, n/2);
			x = GET(n/2+1, i-1); 
			int len = n/2-(i-1-(n/2+1)+1);
			x.fi = mul(x.fi, ex(key[0], len, 0), mod[0]);
			x.se = mul(x.se, ex(key[1], len, 1), mod[1]);
			pii te = GET(i+1, n);
			chsum(x.fi, te.fi, mod[0]); chsum(x.se, te.se, mod[1]);
		}
		// cout << i << " i\n";
		// cout << x.fi << ' ' << x.se <<' ' << y.fi << ' ' << y.se << " pp\n";
		if(x==y){
			m[x] = i;
		}
	}
	if(m.size()==0) cout << "NOT POSSIBLE\n";
	else if(m.size()>=2) cout << "NOT UNIQUE\n";
	else {
		int idx = (*(m.begin())).se, cnt = 0;
		for(int i=1; i<=n; i++){
			if(i==idx) continue;
			if(cnt<n/2) cout << s[i];
			cnt++;
		}
		cout << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...