Submission #167207

#	Time	Username	Problem	Language	Result	Execution time	Memory
167207		ryansee	Three Friends (BOI14_friends)	C++14	35 / 100	984 ms	13468 KiB

friends

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i, s, e) for(ll i=s;i<=ll(e);++i)
#define DEC(i, s, e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (300006)
ll base=37, mod=1e9+7;
ll qexp(ll x,ll e) {
	if(e==0) return 1;
	ll half=qexp(x,e>>1);
	half*=half, half%=mod;
	if(e&1) half*=x, half%=mod;
	return half;
}
ll a, b, c, d, f_b4, s_b4;
ll inv[(int)1e6 + 5];
#define gc getchar_unlocked
void in(ll &x) {
	x=0;
	char ch=gc();
	while(ch<'0'||ch>'9') ch=gc();
	while(ch>='0'&&ch<='9') {
		x=(x<<3)+(x<<1)+ch-48;
		ch=gc();
	}
}
void in(string &A) {
	A="";
	char ch=gc();
	while(ch<'A'||ch>'Z') ch=gc();
	while(ch>='A'&&ch<='Z') {
		A+=ch;
		ch=gc();
	}
}
int main()
{
	FAST
	ll n; in(n);
	string A; in(A);
	for(auto &i:A) i=tolower(i);
	ll pos=-1;
	ll hsh = mod;
	if(n%2==0) { cout<<"NOT POSSIBLE\n"; return 0; }
	ll half = n/2;
	inv[(int)1e6 + 4] = qexp(base,mod-2);
	FOR(i,0,half-1) {
		inv[i]=qexp(base, i);
	}
	FOR(i,1,half) {
		b+=(A[i]-'a'+1) * inv[i-1] % mod, b%=mod;
	}
	FOR(i,half+1,n-1) {
		d+=(A[i]-'a'+1) * inv[i-half-1]%mod, d%=mod;
	}
	FOR(i,0,n-1) {
		if((a+b*inv[f_b4]%mod)%mod == (c+d*inv[s_b4]%mod)%mod) {
			if(hsh != mod && hsh != (a+b*inv[f_b4]%mod)%mod) {
				cout<<"NOT UNIQUE\n"; return 0;
			}
			hsh=(a+b*inv[f_b4]%mod)%mod;
			pos=i; 
		}
		if(i!=n-1) {
			if(f_b4 == half) {
				c+=(A[i]-'a'+1) * inv[s_b4] % mod, c %= mod;
				++ s_b4;
				d-=(A[i+1]-'a'+1), d+=mod, d%=mod;
				d*=inv[(int)1e6 + 4], d%=mod;
			} else {
				a+=(A[i]-'a'+1) * inv[f_b4] % mod, a %= mod;
				if(f_b4 == half) {
					d-=(A[i+1]-'a'+1), d+=mod, d%=mod;
					d*=inv[(int)1e6 + 4], d%=mod;
				} else {
					b-=(A[i+1]-'a'+1), b+=mod, b%=mod;
					b*=inv[(int)1e6 + 4], b%=mod;
				}
				++ f_b4;
			}
		}
	}
	if(pos == -1) {
		cout<<"NOT POSSIBLE\n"; return 0;
	}
	ll co = 0;
	FOR(i,0,n-1) if(i^pos) {
		cout<<(char)toupper(A[i]);
		++ co;
		if(co == half) return 0;
	}
}

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