Submission #284783

#	Time	Username	Problem	Language	Result	Execution time	Memory
284783		ChrisT	Three Friends (BOI14_friends)	C++17	100 / 100	134 ms	20984 KiB

friends

#include <bits/stdc++.h>
using namespace std;
const int MN = 2e6 + 5, MOD = 1e9 + 9, BASE = 143;
char s[MN]; int pw[MN], hsh[MN];
int substr (int l, int r) {
	if (r < l) return 0;
	int ret = hsh[r] - (long long)hsh[l-1] * pw[r-l+1] % MOD;
	if (ret < 0) ret += MOD;
	return ret;
}
int main () {
	int n;
	scanf ("%d",&n);
	scanf ("%s",s+1);
	if (!(n&1)) return !printf ("NOT POSSIBLE\n");
	pw[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = (long long)pw[i-1] * BASE % MOD;
		hsh[i] = ((long long)hsh[i-1] * BASE + s[i] - 'A' + 1) % MOD;
	}
	int has = -1, where = -1;
	for (int i = 1; i <= (n+1)/2; i++) {
		int lhsh = ((long long)substr(1,i-1) * pw[n/2 - i + 1] + substr(i+1,n/2+1)) % MOD;
		int rhsh = substr(n/2+2,n);
		if (lhsh == rhsh) {
			if (~has && has != lhsh) return !printf ("NOT UNIQUE\n");
			has = lhsh; where = i;
		}
	}
	for (int i = n/2+2; i <= n; i++) {
		int lhsh = substr(1,n/2);
		int rhsh = ((long long)substr((n+1)/2,i-1) * pw[n-i] + substr(i+1,n)) % MOD;
		if (lhsh == rhsh) {
			if (~has && has != lhsh) return !printf ("NOT UNIQUE\n");
			has = lhsh; where = i;
		}
	}
	if (where == -1) return !printf ("NOT POSSIBLE\n");
	if (where > n/2) {
		for (int i = 1; i <= n/2; i++) printf ("%c",s[i]);
		printf ("\n");
	} else {
		for (int i = n/2+2; i <= n; i++) printf ("%c",s[i]);
		printf ("\n");
	}
	return 0;
}

Compilation message (stderr)

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

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