Submission #38079

#	Time	Username	Problem	Language	Result	Execution time	Memory
38079		wzy	Three Friends (BOI14_friends)	C++14	100 / 100	499 ms	86660 KiB

friends

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define int long long // LEMBRAR DE TROCAR CASO PROBLEMA DE MEMORIA
#define pii pair<int,int>
#define eps (int) 1e9
#define mp make_pair
#define pb push_back
int base = 57 , mod = 1000000007 , ivi = 58394161;
int hs[3000000], pot[3000000] , inv[3000000];
int gethash(int l , int r){
	if(l > r) return 0;
	int hashlow = hs[r];
	if(l) hashlow -= hs[l-1];
	hashlow += mod*mod;
	hashlow %= mod;
	hashlow *= inv[l];
	hashlow %= mod;
	return hashlow;
}

int binaryexpo(int x , int y){
	if(x == 0) return 0;
	if(y==0)return 1;
	if(y == 1) return x;
	int pp = binaryexpo(x , y/2);
	pp *= pp;
	pp %= mod;
	if(y %2) pp*=x;
	pp%= mod;
	return pp;
} 


int32_t main(){
	/*ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	*/
	int n;
	scanf("%lld" , &n);
	string s;
	s.resize(n);
	scanf("%s" , &s[0]);
	if(n%2 == 0 || n == 1){
		printf("NOT POSSIBLE\n");
		return 0;
	}
	ivi = binaryexpo(base , mod - 2);
	pot[0] = 1 , pot[1] = base, inv[0] = 1 , inv[1] = ivi;
	for(int i = 2 ; i < 3000000; i ++){
		pot[i] = pot[i-1] * base;
		inv[i] = inv[i-1] * ivi;
		inv[i] %= mod;
		pot[i] %= mod;
	}
	hs[0] = (s[0] - 'A' + 1);
	for(int i = 1 ; i < n; i ++){
		hs[i] = (s[i] - 'A' + 1)*pot[i];
		hs[i] += hs[i-1];
		hs[i] += mod*mod;
		hs[i] %= mod;
	}
	vector<int> can_r;
	set<int> hashz;

	for(int i = 0 ; i < n; i ++){
		if(n/2 == i){
			if(gethash(0 , i-1) == gethash(i + 1 , n-1)) can_r.pb(i), hashz.insert(gethash(0 , i-1));

		}
		if(i < n/2){
			if((gethash(n/2 + 1 , n-1)%mod) == ((gethash(0 , i -1) + gethash(i + 1 , n/2)*pot[i])%mod)) can_r.pb(i)  , hashz.insert(gethash(n/2 + 1 , n - 1)%mod);
		}
		if(i > n/2){
			if((gethash(0 , n/2 - 1)%mod) == ( (gethash(n/2  , i-1) + gethash(i + 1 , n -1)*pot[i  - n/2]))) can_r.pb(i) , hashz.insert(gethash(0 , n/2 - 1)%mod) ;
		}
	}
	if(hashz.size() == 0) printf("NOT POSSIBLE\n");
	if(hashz.size() > 1) printf("NOT UNIQUE\n");
	if(hashz.size() == 1){
		int conta = n - 1;
		conta /= 2;
		int tt = 0;
			while(conta){
			if(tt++ == can_r[0]) continue;
			printf("%c" , s[tt-1]);
			conta--;
		}
	}

}

Compilation message (stderr)

friends.cpp: In function 'int32_t main()':
friends.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
                    ^
friends.cpp:44:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s" , &s[0]);
                     ^

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