Submission #208643

#	Time	Username	Problem	Language	Result	Execution time	Memory
208643		E869120	Three Friends (BOI14_friends)	C++14	35 / 100	117 ms	13024 KiB

friends

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

long long mod = 2147483647;

int N; string S;
long long power[1 << 18];
long long hush[1 << 18];

void init() {
	power[0] = 1;
	for (int i = 1; i <= 250000; i++) power[i] = 217LL * power[i - 1] % mod;
	for (int i = 1; i <= S.size(); i++) hush[i] = (217LL * hush[i - 1] + (long long)(S[i - 1] - 'A' + 1)) % mod;
}

long long getval(int l, int r) {
	return (hush[r] - (hush[l] * power[r - l]) + mod * mod) % mod;
}

int main() {
	cin >> N >> S; init();
	if (N % 2 == 0) {
		cout << "NOT POSSIBLE" << endl;
		return 0;
	}

	vector<long long> val; int turn = 0;
	for (int i = 0; i < N; i++) {
		long long s1, s2;
		if (i < N / 2) {
			s1 = getval(0, i) * power[(N / 2) - i] + getval(i + 1, (N / 2) + 1); s1 %= mod;
			s2 = getval((N / 2) + 1, N);
		}
		else if (i == N / 2) {
			s1 = getval(0, i);
			s2 = getval(i + 1, N);
		}
		else {
			s1 = getval(0, N / 2);
			s2 = getval(N / 2, i) * power[N - i - 1] + getval(i + 1, N); s2 %= mod;
		}
		if (s1 == s2) { val.push_back(s1); turn = i; }
	}
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());

	if (val.size() == 0) cout << "NOT POSSIBLE" << endl;
	if (val.size() >= 2) cout << "NOT UNIQUE" << endl;
	if (val.size() == 1) {
		if (turn <= N / 2) cout << S.substr((N / 2) + 1, N - ((N / 2) + 1)) << endl;
		else cout << S.substr(0, N / 2) << endl;
	}
	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'void init()':
friends.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= S.size(); i++) hush[i] = (217LL * hush[i - 1] + (long long)(S[i - 1] - 'A' + 1)) % mod;
                  ~~^~~~~~~~~~~

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