Submission #103472

#	Time	Username	Problem	Language	Result	Execution time	Memory
103472		wilwxk	세 명의 친구들 (BOI14_friends)	C++11	0 / 100	177 ms	64940 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;
const int P2=43;
char v[MAXN];
ll h[2][MAXN], pot[2][MAXN];
unordered_set<ll> s;
int n;

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

ll junta(ll a, ll b, int tam, int k) {
	if(tam==0) return b;
	if(tam==n/2) return a;
	tam=(n/2)-tam;
	ll val=a*pot[k][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][0]=1; pot[1][0]=1;
	for(int i=1; i<=n; i++) {
		h[0][i]=h[0][i-1]*P; h[0][i]+=(v[i]-'A'+1);
		h[0][i]%=MOD;
		h[1][i]=h[1][i-1]*P2; h[1][i]+=(v[i]-'A'+1);
		h[1][i]%=MOD;

		pot[0][i]=pot[0][i-1]*P; pot[0][i]%=MOD;
		pot[1][i]=pot[1][i-1]*P2; pot[1][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; ll aa2, bb2;
		if(i<=(n+1)/2) {
			aa=junta( gh(1, i-1, 0), gh(i+1, n/2+1, 0), i-1, 0);
			bb=gh(n/2+2, n, 0);
			aa2=junta( gh(1, i-1, 1), gh(i+1, n/2+1, 1), i-1, 1);
			bb2=gh(n/2+2, n, 1);
			// 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, 0);
			bb=junta( gh(n/2+1, i-1, 0) , gh(i+1, n, 0), i-n/2-1, 0);
			aa2=gh(1, n/2, 1);
			bb2=junta( gh(n/2+1, i-1, 1) , gh(i+1, n, 1), i-n/2-1, 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&&aa2==bb2) {
			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:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
friends.cpp:34: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