Submission #44530

#	Time	Username	Problem	Language	Result	Execution time	Memory
44530		MatheusLealV	Three Friends (BOI14_friends)	C++17	0 / 100	1092 ms	65136 KiB

friends

#include <bits/stdc++.h>
#define N 2000050
#define mod (1000000007)
#define mod2 (982451653)
#define q (879190747)
#define q2 (858599509)
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

int n, opt = -1;

set<ll> ss;

string s, best;

ll hashing[N][2], potq[N], potq2[N];

ll Pow(ll x, ll p, ll modi)
{
	if(!p) return 1;

	ll ans = Pow(x, p/2, modi);

	ans = (ans*ans)%modi;

	if(p & 1) return (ans*x)%modi;

	return (ans);
}

ll inverse(ll x, ll p)
{
	return Pow(x, p - 2, p);
}

void init()
{
	potq[0] = potq2[0] = 1;

	for(int i = 1; i < N; i++) potq[i] = (q*potq[i - 1])%mod;

	for(int i = 1; i < N; i++) potq2[i] = (q2*potq2[i - 1])%mod2;

	for(int i = 0; i < s.size(); i++)
	{
		hashing[i + 1][0] = (hashing[i][0] + s[i]*potq[i + 1])%mod;

		hashing[i + 1][1] = (hashing[i][1] + s[i]*potq2[i + 1])%mod2;
	}
}

ll shift(ll x)
{
	return x*inverse(q, mod);
}

ll getHash(int i, int j, int b)
{
	i ++, j ++, b ++;

	ll esq = 0, dir = 0;

	if(i <= b && b <= j)
	{
		esq = (mod + hashing[b - 1][0] - hashing[i - 1][0])%mod;

		esq = (esq * inverse(potq[i], mod))%mod;

		dir = (mod + hashing[j][0] - hashing[b][0])%mod;

		dir = (dir * inverse(potq[b + 1], mod))%mod;

		dir = (dir * potq[b - 1]) % mod;
		
		return (esq + dir)%mod;
	}

	ll H = (mod + hashing[j][0] - hashing[i - 1][0])%mod;

	ll dH = inverse(potq[i], mod);

	H = (H*dH)%mod;

	return H;
}

string get(int ini, int fim, int block)
{
	string ss = "";

	for(int i = ini; i <= fim; i++)
		if(i != block) ss.push_back(s[i]);

	return ss;
}

int main()
{
	//ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	cin>>s;

	if(s.size() % 2 == 0)
	{
		cout<<"NOT POSSIBLE\n";

		return 0;
	}

	init();

	for(int p = 0; p < n; p++)
	{
		int l1 = 0, r1 = (n/2) - 1;

		int l2 = (n/2) + 1, r2 = n - 1;

		if(p <= r1) r1 ++;

		else if(p >= l2) l2 --;

		ll esq = getHash(l1, r1, p), dir = getHash(l2, r2, p);

		if(esq == dir) ss.insert(esq), opt = p;
	}

	for(int p = 0; p < n; p++)
	{
		if(p != opt) continue;

		int l1 = 0, r1 = (n/2) - 1;

		int l2 = (n/2) + 1, r2 = n - 1;

		if(p <= r1) r1 ++;

		else l2 --;

		best = get(l1, r1, p);
	}

	if(ss.size() == 0) cout<<"NOT POSSIBLE\n";

	else if(ss.size() == 1) cout<<best<<'\n';

	else cout<<"NOT UNIQUE\n";
}

Compilation message (stderr)

friends.cpp: In function 'void init()':
friends.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++)
                 ~~^~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:138:23: warning: unused variable 'r2' [-Wunused-variable]
   int l2 = (n/2) + 1, r2 = n - 1;
                       ^~

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