Submission #167207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167207	2019-12-06T15:27:03 Z	ryansee	Three Friends (BOI14_friends)	C++14	35 / 100	500 ms	13468 KB

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.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	376 KB	Output is correct
29	Correct	2 ms	484 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	2 ms	376 KB	Output is correct
33	Correct	2 ms	376 KB	Output is correct
34	Correct	2 ms	376 KB	Output is correct
35	Correct	2 ms	376 KB	Output is correct
36	Correct	2 ms	376 KB	Output is correct
37	Correct	2 ms	376 KB	Output is correct
38	Correct	2 ms	376 KB	Output is correct
39	Correct	2 ms	376 KB	Output is correct
40	Correct	2 ms	376 KB	Output is correct
41	Correct	2 ms	376 KB	Output is correct
42	Correct	2 ms	436 KB	Output is correct
43	Correct	2 ms	376 KB	Output is correct
44	Correct	3 ms	376 KB	Output is correct
45	Correct	3 ms	436 KB	Output is correct
46	Correct	3 ms	376 KB	Output is correct
47	Correct	3 ms	376 KB	Output is correct
48	Correct	3 ms	504 KB	Output is correct
49	Correct	2 ms	376 KB	Output is correct
50	Correct	3 ms	376 KB	Output is correct
51	Correct	3 ms	376 KB	Output is correct
52	Correct	3 ms	504 KB	Output is correct
53	Correct	3 ms	376 KB	Output is correct
54	Correct	3 ms	376 KB	Output is correct

Subtask #2

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	984 ms	13468 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-