Submission #700993

#	Time	Username	Problem	Language	Result	Execution time	Memory
700993		Doncho_Bonboncho	Three Friends (BOI14_friends)	C++14	0 / 100	895 ms	88668 KiB

friends

#include <bits/stdc++.h>
#include <unordered_set>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

const int C = 33;

int alpfC[32];

std::unordered_map<ll, int> m;

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	int n;
	std::cin>>n;
	std::string s;
	std::cin>>s;

	for( int i=0 ; i<s.size() ; i++ ) s[i] += 'a' - 'A';

	//std::cerr<<" ! "<<s<<"\n";

	if( !(n%2) ){
		std::cout<<"NOT POSSIBLE\n";
		return 0;
	}

	int nStr = (n-1)/2;
	ll step = 1;
	for( int i=1 ; i<nStr ; i++ ) step *= C;
	for( int i=1 ; i<26 ; i++ ) alpfC[i] = alpfC[i-1] + step;

	ll currHash = 0;
	for( int i=0 ; i<nStr ; i++ ){

		currHash *= C;
		currHash %= mod;

		currHash += s[i]-'a';
		if( currHash >= mod ) currHash -= mod;
	}
	ll hashNext = currHash - ( s[nStr-1] - 'a');
	hashNext += s[nStr] - 'a';
	m[hashNext] = 2;
	
	//std::cerr<<" ! "<<currHash<<" , "<<hashNext<<"\n";

	int endNas = -1;
	int type = -1;
	int num = 0;
	

	m[currHash] = 1;
	for( int i=nStr ; i<n ; i++ ){

	//	std::cerr<<" - "<<s[i-nStr]<<" -> "<<alpfC[s[i-nStr]-'a']<<"\n";
		currHash -= alpfC[s[i-nStr]-'a'];
		if( currHash < 0 ) currHash += mod;

	//	std::cerr<<" * "<<currHash<<" * "<<C<<"\n";

		currHash *= C;
		currHash %= mod;

		ll hashNext = currHash;

		currHash += s[i] - 'a';
		if( currHash >= mod ) currHash -= mod;
	//	std::cerr<<" + "<<s[i]<<" "<<s[i] - 'a'<<"\n";

		if( i != n-1 ) hashNext += s[i+1] - 'a';
	//	std::cerr<<" + "<<s[i+1]<<" "<<s[i+1] - 'a'<<"\n";
		if( hashNext >= mod ) hashNext -= mod;

	//	std::cerr<<" $ "<<currHash<<" "<<hashNext<<"\n";

		if( m[currHash] != 0 ){
			endNas = i;
			type = 1;
			num++;
		}
		if( i != n-1 and m[hashNext] == 1 ){
			endNas = i;
			type = 2;
			num++;
		}

		m[currHash] = 1;
		if( !m[hashNext] ) m[hashNext] = 2;
	}

	for( int i=0 ; i<n ; i++ ) s[i] -= 'a' - 'A';

	if( num == 0 ) std::cout<<"NO POSSIBLE";
	else if( num > 1 ) std::cout<<"NO UNIQUE";
	else{
		if( type == 1 ){
			std::cout<<s.substr( endNas - nStr+1, endNas );
		}else{
			/*
			std::cout<<s.substr( endNas - nStr+1, endNas-3 );
			std::cout<<s[endNas+1];
			*/
	//		std::cerr<<endNas<<", "<<nStr<<"\n";
			int st = endNas - nStr;
			for( int i=st+1 ; i<st + nStr ; i++ ) std::cout<<s[i];
			std::cout<<s[endNas+1];
		}
	}

	std::cout<<"\n";

	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for( int i=0 ; i<s.size() ; i++ ) s[i] += 'a' - 'A';
      |                 ~^~~~~~~~~

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