Submission #794343

#	Time	Username	Problem	Language	Result	Execution time	Memory
794343		bane	Three Friends (BOI14_friends)	C++17	0 / 100	875 ms	85332 KiB

friends

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/


#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)


#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'

 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
 
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

const int nax = (int)2000002;

int n, p = 31, m = (int)1e9 + 7;
ll hsh[nax];
string s;

ll bpow(ll u, ll b){
	ll res = 1;
	while(b){
		if (b & 1)res = (res * u)%m;
		b /= 2;
		u*=u;
		u%=m;
	}
	return res;
}

ll inv(ll p){
	return bpow(p,m-2);
}

void solve(){
	cin >> n >> s;
	if (n % 2 == 0){
		cout << "NOT POSSIBLE" << endl;
		return;
	}
	ll ps[n+1];
	ps[0] = 1;
	for (int i = 1; i <= n; i++){
		ps[i] = p;
		ps[i] *= ps[i - 1];
		ps[i] %= m;
	}
	ll ips[n + 1];
	for (int i = 0; i <= n; i++){
		ips[i] = inv(ps[i]);
	}
	for (int i = 0; i < n; i++){
		hsh[i] = (s[i] - 'A' + 1) * ps[i] % m;
		if (i)hsh[i] += hsh[i - 1];
		hsh[i]%=m;
	}
	//cout << hsh[0] << endl;
	//cout << ps[3] << endl;
	int L1[n], R1[n], L2[n], R2[n];
	unordered_set<ll>se;
	string res = "";
	for(int i = 0; i < n; i++){
		L1[i] = 0;
		if (i == 0)L1[i]++;
		R1[i] = L1[i] + n / 2 - 1;
		if (R1[i] >= i && L1[i] < i)R1[i]++;
		ll hash1 = 0;
		if (R1[i] > i && L1[i] < i){
			hash1 = (i < 1 ? 0 : hsh[i - 1]);
			hash1 += ((hsh[R1[i]] - hsh[i]) * ips[i + 1]%m)
			* ps[i] % m; 
		}else{
			hash1 = hsh[R1[i]];
			if (L1[i]){
				hash1 -= hsh[L1[i] - 1];
				hash1 %= m;
				hash1 *= ips[L1[i]];
			}
			hash1 %= m;
		}
		L2[i] = R1[i] + 1;
		if (L2[i] == i)++L2[i];
		R2[i] = L2[i] + n / 2 - 1;
		ll hash2 = 0;
		if (R2[i] >= i && L2[i] < i)++R2[i];
		//cout << L1[i] << " " << R1[i] << " " << L2[i] << " " << R2[i] << endl;
		if (L2[i] > i){
			hash2 = hsh[R2[i]] - hsh[L2[i] - 1];
			hash2 *= ips[L2[i]];
			hash2 %= m;
		}else{
			hash2 = hsh[i - 1] - hsh[L2[i] - 1];
			hash2 *= ips[L2[i]];
			hash2 %= m;
			ll hash3 = hsh[R2[i]] - hsh[i];
			hash3 *= ips[i+1];
			hash3 %= m;
			hash3 *= ps[i - L2[i]];
			hash3 %= m;
			if (i - 1 != R2[i]) hash2 += hash3;
		}
		if (hash1 == hash2){
			if (se.empty()){
				for (int j = 0; j < n; j++){
					if (i == j)continue;
					if (res.size() <  n / 2)res += s[j];
					else break;
				}
			}
			se.insert(hash1);
			if (se.size() > 1){
				cout << "NOT UNIQUE" << endl;
				return;
			}

		}
	}
	if (se.empty())cout << "NOT POSSIBLE" << endl;
	else cout << res << endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);	
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'void solve()':
friends.cpp:140:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |      if (res.size() <  n / 2)res += s[j];
      |          ~~~~~~~~~~~^~~~~~~~

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