Submission #103470

#	Time	Username	Problem	Language	Result	Execution time	Memory
103470		wilwxk	Three Friends (BOI14_friends)	C++11	0 / 100	89 ms	33552 KiB

friends

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e6+6;
const ll MOD=1e9+9;
const int P=257;
char v[MAXN];
ll h[MAXN], pot[MAXN];
unordered_set<ll> s;
int n;

int gh(int ini, int fim) {
	if(fim<ini) return 0;
	ll val=h[ini-1]*pot[fim-ini+1];
	val%=MOD;
	val=h[fim]-val; val%=MOD;
	val+=MOD; val%=MOD;
	return val;
}

ll junta(ll a, ll b, int tam) {
	if(tam==0) return b;
	if(tam==n/2) return a;
	tam=(n/2)-tam;
	ll val=a*pot[tam];
	val+=b;
	return val;
}

int main() {
	scanf("%d", &n);
	scanf(" %s", &v[1]);

	if(n%2==0) {
		printf("NOT POSSIBLE\n");
		return 0;
	}

	pot[0]=1;
	for(int i=1; i<=n; i++) {
		h[i]=h[i-1]*P;
		h[i]+=(v[i]-'A');
		h[i]%=MOD;
		pot[i]=pot[i-1]*P;
		pot[i]%=MOD;
	}

	// for(int i=1; i<=n; i++) printf("%d ", pot[i]); printf("\n");
	// printf("ghs %lld e %lld\n", gh(2, 5), gh(4, 7));

	int resp=-1;
	for(int i=1; i<=n; i++) {
		// printf("testando %d\n", i);
		ll aa, bb;
		if(i<=(n+1)/2) {
			aa=junta( gh(1, i-1), gh(i+1, n/2+1), i-1 );
			bb=gh(n/2+2, n);
			// printf("[%d %d] [%d %d] (%d) // [%d %d] >> ", 1, i-1, i+1, (n+1)/2, i-1, (n+1)/2+1, n);
			// printf("%lld %lld\n", aa, bb);
		}
		else {
			aa=gh(1, n/2);
			bb=junta( gh(n/2+1, i-1) , gh(i+1, n), i-n/2-1 );
			// printf("[%d %d] // [%d %d] [%d %d] (%d) >> ", 1, n/2, (n+1)/2, i-1, i+1, n, i-(n+1)/2);
			// printf("%lld %lld\n", aa, bb);
		}

		if(aa==bb) {
			resp=i;
			s.insert(aa);
			if(s.size()>1) {
				printf("NOT UNIQUE\n");
				return 0;
			}
		}
	}

	if(resp==-1) {
		printf("NOT POSSIBLE\n");
		return 0;
	}

	if(resp<=n/2+1) {
		for(int i=1; i<=(n+1)/2; i++) if(i!=resp) printf("%c", v[i]);
	}
	else {
		for(int i=n/2+1; i<=n; i++) if(i!=resp) printf("%c", v[i]);
	}
}

Compilation message (stderr)

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

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