Submission #1024418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024418		ByeWorld	Three Friends (BOI14_friends)	C++14	0 / 100	1063 ms	96372 KiB

friends

#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], inv[MAXN], ex[MAXN];
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[len].fi, mod[0]), mod[0]);
	int s = sub(pr[y].se, mul(pr[x-1].se, ex[len].se, mod[1]), mod[1]);
	return pii(f, s);
}
signed main(){
	inv[0] = {1, 1}; ex[0] = {1, 1};
	for(int i=1; i<=MAXN-5; i++){
		ex[i].fi = mul(ex[i-1].fi, key[0], mod[0]);
		ex[i].se = mul(ex[i-1].se, key[1], mod[1]);
		inv[i].fi = expo(ex[i].fi, mod[0]-2, mod[0]);
		inv[i].se = expo(ex[i].se, mod[1]-2, mod[1]);
	}
	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[len].fi, mod[0]);
			x.se = mul(x.se, ex[len].se, 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[len].fi, mod[0]);
			x.se = mul(x.se, ex[len].se, 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';
	}
}

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