Submission #45134

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

friends

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

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

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

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

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

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

void build(int node, int L, int R)
{
	if(L == R) st[node] = {int(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<int, int> qry(int node, int L, int R, int a, int 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("%d", &n);
	cin >> S;
	build(1, 0, n-1);

	vector<int> ans;
	for(int i = 0;i < n;i++)
	{
		pair<int, int> 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(int(ans.size()) > 1) printf("NOT UNIQUE\n");
	else
	{
		if(ans[0] < n/2) cout << S.substr(n/2+1, ans[0]+1) << "\n";
		else cout << S.substr(0, ans[0]+1) << "\n";
	}
}

Compilation message (stderr)

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

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