Submission #103508

#	Time	Username	Problem	Language	Result	Execution time	Memory
103508		wilwxk	Three Friends (BOI14_friends)	C++11	100 / 100	342 ms	75900 KiB

friends

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN=2e6+6;
const ll MOD=1e9+7;
const ll P=257;
const ll P2=5;
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 a;
	ll val=a*pot[k][tam];
	val%=MOD;
	val+=b;
	return val%MOD;
}
 
bool checa(int k) {
	vector<int> aux;
	for(int i=1; i<=n; i++) if(i!=k) aux.push_back(v[i]);
	for(int i=0; i<n/2; i++) {
		printf("%c", aux[i]);
		if(aux[i]!=aux[i+n/2]) assert(0);
	}
	return 1;
}
 
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]%=MOD;
		h[0][i]+=(v[i]-'A'+1); h[0][i]%=MOD;
		h[1][i]=h[1][i-1]*P2; h[1][i]%=MOD;
		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 %lld %lld >> %lld\n", gh(1, 2, 0), gh(2, 3, 0), gh(2, 5, 0), junta(gh(1, 2, 0), gh(2, 3, 0), 2, 0));
 
	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), n/2-i+1, 0);
			bb=gh(n/2+2, n, 0);
			aa2=junta( gh(1, i-1, 1), gh(i+1, n/2+1, 1), n/2-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, n/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), n-i, 0);
			aa2=gh(1, n/2, 1);
			bb2=junta( gh(n/2+1, i-1, 1) , gh(i+1, n, 1), n-i, 1);
			// printf("[%d %d] // [%d %d] [%d %d] (%d) >> ", 1, n/2, (n+1)/2, i-1, i+1, n, n-i);
			// printf("%lld %lld\n", aa, bb);
		}
 
		if(aa==bb&&aa2==bb2) {
			s.insert(aa2);
			//printf("%d inserindo %lld\n", i, aa);
			if(s.size()>1) {
				printf("NOT UNIQUE\n");
				return 0;
			}
          	resp=i;
		}
	}
 
	if(resp==-1) {
		printf("NOT POSSIBLE\n");
		return 0;
	}
 
	checa(resp);
}

Compilation message (stderr)

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

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