Submission #45137

#	Time	Username	Problem	Language	Result	Execution time	Memory
45137		nibnalin	Three Friends (BOI14_friends)	C++17	0 / 100	76 ms	4816 KiB

friends

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long int lli;

const lli maxn = lli(2e5)+5, MOD = lli(1e9)+11, charsz = 29;

lli n;
string S;
pair<lli, lli> st[4*maxn+10];

lli modpow(lli a, lli b)
{
	if(!b) return 1ll;
	else
	{
		lli res = modpow(a, b/2ll);
		res *= res;
		res %= MOD;
		if(b%2) res *= a%MOD;
		return res%MOD;
	}
}

pair<lli, lli> combine(pair<lli, lli> a, pair<lli, lli> b)
{
	pair<lli, lli> res = {a.first, a.second+b.second};
	res.first += (b.first%MOD*modpow(charsz, a.second)%MOD)%MOD;
	res.first %= MOD;
	return res;
}

inline lli left(lli node) { return (node<<1); }
inline lli right(lli node) { return (node<<1)+1; }

void build(lli node, lli L, lli R)
{
	if(L == R) st[node] = {lli(S[L]-'A'), 1};
	else
	{
		build(left(node), L, (L+R)/2);
		build(right(node), (L+R)/2+1, R);
		st[node] = combine(st[left(node)], st[right(node)]);
	}
}

pair<lli, lli> qry(lli node, lli L, lli R, lli a, lli b)
{
	if(a > R || b < L) return {0, 0};
	else if(a <= L && R <= b) return st[node];
	else return combine(qry(left(node), L, (L+R)/2, a, b), qry(right(node), (L+R)/2+1, R, a, b));
}

int main(void)
{
	scanf("%lld", &n);
	cin >> S;
	build(1, 0, n-1);

	vector<lli> ans;
	for(lli i = 0;i < n;i++)
	{
		pair<lli, lli> h1, h2;
		if(i < n/2)
		{
			h1 = combine(qry(1, 0, n-1, 0, i-1), qry(1, 0, n-1, i+1, n/2));
			h2 = qry(1, 0, n-1, n/2+1, n-1);
		}
		else
		{
			h1 = qry(1, 0, n-1, 0, n/2-1);
			h2 = combine(qry(1, 0, n-1, n/2, i-1), qry(1, 0, n-1, i+1, n-1));
		}
		//cout << i << " " << h1.first << " " << h1.second << " " << h2.first << " " << h2.second << "\n";
		if(h1 == h2) ans.push_back(i);
	}
	if(ans.empty()) printf("NOT POSSIBLE\n");
	else if(lli(ans.size()) > 1) printf("NOT UNIQUE\n");
	else
	{
		if(ans[0] < n/2) cout << S.substr(n/2+1, ans[0]) << "\n";
		else cout << S.substr(0, ans[0]) << "\n";
	}
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~

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