Submission #57431

#	Time	Username	Problem	Language	Result	Execution time	Memory
57431		PeppaPig	Three Friends (BOI14_friends)	C++14	35 / 100	1079 ms	36824 KiB

friends

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e6 + 5;

pii add(pii a, pii b) { return pii(a.x + b.x, a.y + b.y); }
pii sub(pii a, pii b) { return pii(a.x - b.x, a.y - b.y); }
pii mul(pii a, pii b) { return pii(a.x * b.x, a.y * b.y); }

pii prm(69, 1337);
pii pwr[N];

int n, mid;
pii dp[N];
string A;
set<string> ans;

int main() {
	pwr[0] = pii(1, 1);
	for(int i = 1; i < N; i++) pwr[i] = mul(pwr[i - 1], prm);

	scanf("%d", &n);
	if(!(n & 1)) return !printf("NOT POSSIBLE");
	mid = n >> 1;
	cin >> A;

	for(int i = 1; i <= n; i++) dp[i] = add(mul(dp[i - 1], prm), pii(A[i - 1], A[i - 1]));
	for(int i = 1; i <= n; i++) {
		pii lhs, rhs;
		if(i <= mid) {
			lhs = add(mul(dp[i - 1], pwr[mid - i + 1]), sub(dp[mid + 1], mul(dp[i], pwr[mid - i + 1])));
			rhs = sub(dp[n], mul(dp[mid + 1], pwr[mid]));
			if(lhs == rhs) ans.emplace(A.substr(mid + 1, mid));
		} else {
			lhs = dp[mid];
			rhs = add(mul(sub(dp[i - 1], mul(dp[mid], pwr[i - mid - 1])), pwr[n - i]), sub(dp[n], mul(dp[i], pwr[n - i])));
			if(lhs == rhs) ans.emplace(A.substr(0, mid));
		}
	}
	if(!ans.size()) return !printf("NOT POSSIBLE");
	else if(ans.size() == 1) cout << *ans.begin();
	else if(ans.size() > 1) return !printf("NOT UNIQUE");

	return 0;
}

Compilation message (stderr)

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

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