제출 #844992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844992		vjudge1	세 명의 친구들 (BOI14_friends)	C++17	100 / 100	48 ms	66812 KiB

friends

#include <bits/stdc++.h>
using namespace std;
#define int long long  

const int N = 2e6 + 21;

const int base_1 = 29;
const int base_2 = 31;
const int base_3 = 37;

const int mod_1 = 998244353;
const int mod_2 = 1e9 + 7;
const int mod_3 = 1e9 + 9;

int n;
int Pow[N][4];

pair <int , pair <int , int>> prefix , suffix;

string s;

pair <int , pair <int , int>> get_hash(string s) {
	int pow_1 = 0;
	int pow_2 = 0;
	int pow_3 = 0;
	for(int i = 0; i < s.size(); i++) {
		pow_1 = (pow_1 * base_1 + (s[i] - 'A' + 1)) % mod_1;
		pow_2 = (pow_2 * base_2 + (s[i] - 'A' + 1)) % mod_2;
		pow_3 = (pow_3 * base_3 + (s[i] - 'A' + 1)) % mod_3;
	}
	return make_pair(pow_1 , make_pair(pow_2 , pow_3));
}

bool check_prefix() {
	int pow_1 = suffix.first;
	int pow_2 = suffix.second.first;
	int pow_3 = suffix.second.second;
	for(int i = n / 2 , j = n / 2 - 1; i < n - 1; i++ , j--) {
		pow_1 = (pow_1 + (s[i] - s[i + 1]) * Pow[j][1] + mod_1 * mod_1) % mod_1;
		pow_2 = (pow_2 + (s[i] - s[i + 1]) * Pow[j][2] + mod_2 * mod_2) % mod_2;
		pow_3 = (pow_3 + (s[i] - s[i + 1]) * Pow[j][3] + mod_3 * mod_3) % mod_3;
		if(make_pair(pow_1 , make_pair(pow_2 , pow_3)) == prefix) {	
			return true;
		}
	}
	return false;
}

bool check_suffix() {
	int pow_1 = prefix.first;
	int pow_2 = prefix.second.first;
	int pow_3 = prefix.second.second;
	for(int i = n / 2 , j = 0; i > 0; i-- , j++) {
		pow_1 = (pow_1 + (s[i] - s[i - 1]) * Pow[j][1] + mod_1 * mod_1) % mod_1;
		pow_2 = (pow_2 + (s[i] - s[i - 1]) * Pow[j][2] + mod_2 * mod_2) % mod_2;
		pow_3 = (pow_3 + (s[i] - s[i - 1]) * Pow[j][3] + mod_3 * mod_3) % mod_3;
		if(make_pair(pow_1 , make_pair(pow_2 , pow_3)) == suffix) {
			return true;
		}
	}
	return false;
}

main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);	
	cin >> n;
	cin >> s;
	if(n % 2 == 0) {
		cout << "NOT POSSIBLE" << '\n';
		return 0;	
	}

	Pow[0][1] = Pow[0][2] = Pow[0][3] = 1;
	for(int i = 1; i <= N; i++) {
		Pow[i][1] = (Pow[i - 1][1] * base_1) % mod_1;
		Pow[i][2] = (Pow[i - 1][2] * base_2) % mod_2;
		Pow[i][3] = (Pow[i - 1][3] * base_3) % mod_3;
	}

	prefix = get_hash(s.substr(0 , n / 2));
	suffix = get_hash(s.substr(n / 2 + 1 , n / 2));
	if(prefix == suffix) {
		cout << s.substr(n / 2 + 1 , n / 2) << '\n';
		return 0;
	}
	bool check_1 = check_prefix();
	bool check_2 = check_suffix();
	if(check_1 ^ check_2) {
		if(check_1 == true) {
			cout << s.substr(0 , n / 2) << '\n';
		}
		else {
			cout << s.substr(n / 2 + 1 , n / 2) << '\n';
		}
	}
	else {
		cout << "NOT" << ' ';
		if(check_1 == true) {
			cout << "UNIQUE";
		}
		else cout << "POSSIBLE";
		cout << '\n';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

friends.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > get_hash(std::string)':
friends.cpp:26:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i < s.size(); i++) {
      |                 ~~^~~~~~~~~~
friends.cpp: At global scope:
friends.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main() {
      | ^~~~
friends.cpp: In function 'int main()':
friends.cpp:78:13: warning: iteration 2000020 invokes undefined behavior [-Waggressive-loop-optimizations]
   78 |   Pow[i][1] = (Pow[i - 1][1] * base_1) % mod_1;
      |   ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
friends.cpp:77:19: note: within this loop
   77 |  for(int i = 1; i <= N; i++) {
      |                 ~~^~~~

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