Submission #481161

#	Time	Username	Problem	Language	Result	Execution time	Memory
481161		Sohsoh84	Three Friends (BOI14_friends)	C++17	100 / 100	114 ms	40396 KiB

friends

//: // ////: ///  / : //// / :
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 3e6 + 10;
const ll P = 78;
const ll MOD = 1e9 + 7;

int n, ans = MAXN, f = MAXN;
ll pw[MAXN], h1, h2, suff[MAXN];
string s;

inline ll hsh(string s) {
	ll ans = 0;
	for (char c : s)
		ans = (ans * P + int(c)) % MOD;
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	if (!(n & 1)) return cout << "NOT POSSIBLE" << endl, 0;

	string t;
	for (int i = 0; i < n / 2; i++) t.push_back(s[i]);
	h1 = hsh(t + t);
	
	t.clear();
	for (int i = n - 1; i > n - 1 - n / 2; i--)
		t.push_back(s[i]);
	reverse(all(t));
	h2 = hsh(t + t);

	pw[0] = 1;
	for (int i = 1; i < n + 10; i++)
		pw[i] = pw[i - 1] * P % MOD;
	
	for (int i = n - 1; i >= 0; i--)
		suff[i] = (suff[i + 1] + s[i] * pw[n - 1 - i]) % MOD;

	ll h = 0;
	for (int i = 0; i < n; i++) {
		ll th = (h * pw[n - i - 1] + suff[i + 1]) % MOD;
		if (th == h1 || th == h2) {
			if (ans == MAXN) ans = i, f = th;
			else if (f != th) return cout << "NOT UNIQUE" << endl, 0;
		}

		h = (h * P + s[i]) % MOD;
	}

	if (ans == MAXN) return cout << "NOT POSSIBLE" << endl, 0;
	s.erase(s.begin() + ans);
	for (int i = 0; i < n / 2; i++) s.pop_back();
	cout << s << endl;
	return 0;
}

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