Submission #47423

#	Time	Username	Problem	Language	Result	Execution time	Memory
47423		win11905	Three Friends (BOI14_friends)	C++11	100 / 100	288 ms	40684 KiB

friends

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

// I will use hsh 107, 109

const int N = 2e6+5, M = 1e9+7;
int n, st;
char A[N];
pii hsh[N], pw[N], iden(1000000007, 1000000009);

pii add(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 sub(pii a, pii b) { return pii(a.x - b.x, a.y - b.y); }

int main() {
	scanf("%d", &n);
	scanf("%s", A+1);
	st = n >> 1;
	for(int i = 1; i <= n; ++i) hsh[i] = add(mul(hsh[i-1], iden), pii(A[i], A[i]));
	pw[0] = pii(1, 1);
	for(int i = 1; i <= n; ++i) pw[i] = mul(pw[i-1], iden);
	set<pii> V;
	for(int i = 1; i <= n; ++i) {
		pii hshl, hshr;
		if(i <= st) {
			hshl = add(mul(hsh[i-1], pw[st-i+1]), sub(hsh[st+1], mul(hsh[i], pw[st-i+1])));
			hshr = sub(hsh[n], mul(hsh[st+1], pw[st]));
			if(hshl == hshr) V.emplace(st+2, n);
		} else {
			hshl = hsh[st];
			hshr = add(sub(hsh[n], mul(hsh[i], pw[n-i])), 
				mul(sub(hsh[i-1], mul(hsh[st], pw[i-st-1])), pw[n-i]));
			if(hshl == hshr) V.emplace(1, st);
		}
	}
	bool hell = true;
	for(int i = 1; i <= st; ++i) hell &= A[i] == A[st+i+1];
	if(V.size() == 0 or n % 2 == 0) puts("NOT POSSIBLE");
	else if(V.size() == 1 || hell)  A[V.begin()->y+1] = 0, puts(A+V.begin()->x);
	else if(V.size() > 1) puts("NOT UNIQUE");
}

Compilation message (stderr)

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

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