Submission #1098814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098814		Alihan_8	Three Friends (BOI14_friends)	C++17	0 / 100	115 ms	24752 KiB

friends

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int Mod = 998244353, P = 43;

signed main(){
	int n; cin >> n;
	
	string s; cin >> s;
	
	if ( n % 2 == 0 ){
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	
	vector <int> pw(1, 1);
	
	while ( (int)pw.size() <= n ){
		pw.pb(pw.back() * 1LL * P % Mod);
	}
	
	vector <int> p(n + 1);
	
	for ( int i = 0; i < n; i++ ){
		p[i + 1] = (p[i] * 1LL * P + s[i] - 'A' + 1) % Mod;
	}
	
	auto get = [&](int l, int r){
		return ((p[r + 1] - p[l] * 1LL * pw[r - l + 1] % Mod) + Mod) % Mod;
	};
	
	int j = -1, k = n / 2;
	
	for ( int i = 0; i < n; i++ ){
		int x = 0, y = 0;
		
		if ( i >= k ){
			x = get(0, k - 1);
			y = (get(n - k - 1, i - 1) * 1LL * pw[n - i - 1] + get(i + 1, n - 1)) % Mod;
		} else{
			y = get(n - k, n - 1);
			x = (get(0, i - 1) * 1LL * pw[k - i] + get(i + 1, k)) % Mod; 
		}
		
		if ( x == y ){
			if ( j != -1 ){
				cout << "NOT UNIQUE\n";
				return 0;
			}
			
			j = i;
		}
	}
	
	if ( j == -1 ){
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	
	string ans;
	
	for ( int i = 0; i < n; i++ ){
		if ( i != j ) ans += s[i];
	}
	
	for ( int i = 0; i < k; i++ ){
		cout << ans[i];
	}
	
	cout << '\n';
}

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