Submission #1295733

#TimeUsernameProblemLanguageResultExecution timeMemory
1295733Jawad_Akbar_JJThree Friends (BOI14_friends)C++20
100 / 100
91 ms35212 KiB
#include <iostream>

using namespace std;
#define int long long
int h[2<<20], pw[2<<20], mod = 998244353;

int get(int l, int r){
	return (h[r] - h[--l] * pw[r - l] % mod + mod) % mod;
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, id = -1, Vl = 0;
	string s;
	cin>>n>>s;

	for (int i=pw[0]=1;i<=n;i++){
		pw[i] = pw[i-1] * 256 % mod;
		h[i] = (h[i-1] * 256 + s[i-1]) % mod;
	}

	for (int i=1;i<=n and n % 2;i++){
		int h1, h2;
		if (i <= n / 2){
			h1 = (get(1, i-1) * pw[n / 2 - (i - 1)] + get(i + 1, n / 2 + 1)) % mod;
			h2 = get(n / 2 + 2, n);
		}
		else{
			h1 = get(1, n / 2);
			h2 = (get(n / 2 + 1, i - 1) * pw[n - i] + get(i + 1, n)) % mod;
		}
		if (h1 == h2 and id == -1)
			id = i, Vl = h1;
		else if (h1 == h2 and Vl != h1)
			return cout<<"NOT UNIQUE\n", 0;
	}
	if (id == -1)
		return cout<<"NOT POSSIBLE\n", 0;

	for (int i=1;i<=n / 2;i++){
		if (i == id)
			n += 2;
		else
			cout<<s[i-1];
	}
	cout<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...