oj.uz

Submission #700993

# Submission time Handle Problem Language Result Execution time Memory
700993 2023-02-19T15:54:55 Z Doncho_Bonboncho Three Friends (BOI14_friends) C++14
0 / 100
 500 ms 88668 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Execution timed out 895 ms 88668 KB Time limit exceeded
2 Halted 0 ms 0 KB -