Submission #24320

#	Time	Username	Problem	Language	Result	Execution time	Memory
24320		Bruteforceman	세 명의 친구들 (BOI14_friends)	C++11	0 / 100	73 ms	37464 KiB

friends

#include "bits/stdc++.h"
using namespace std;
int n;
string s;

const int mod = 1000000000 + 7;
const int base = 31;
long long p[2000010];
long long power[2000010];

long long hasher(int x, int y) {
	if(x > y) return 0;
	long long ans = (p[y] - power[y-x+1] * p[x-1]) % mod;
	if(ans < 0) ans += mod;
	return ans;
}

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie(0);

	cin >> n;
	cin >> s;
	n = s.size();
	s = "&" + s;

	power[0] = 1;
	p[0] = 0;
	for(int i = 1; i <= n; i++) {
		p[i] = p[i-1] * base + (s[i] - 'A');
		p[i] %= mod; 
		power[i] = power[i-1] * base;
		power[i] %= mod;
	}

	vector <int> can;
	for(int i = 1; i <= (n>>1); i++) {
		long long p1 = hasher(1, i-1);
		long long p2 = hasher(i+1, (n>>1) + 1);
		long long whole = p1 * power[(n >> 1) - i + 1] + p2;
		whole %= mod;
		if(whole == hasher((n >> 1) + 2, n)) {
			can.push_back(i);
		}
	}
	for(int i = (n>>1) + 1; i <= n; i++) {
		long long p1 = hasher((n>>1) + 1, i-1);
		long long p2 = hasher(i+1, n);
		long long whole = p1 * power[n - i] + p2;
		whole %= mod;
		if(whole == hasher(1, n >> 1)) {
			can.push_back(i);
		}
	}
	if(can.empty()) {
		cout << "NOT POSSIBLE" << endl;
	} else if (can.size() == 1) {
		s.erase(s.begin() + can.front());
		for(int i = 1; i <= (n>>1); i++) {
			cout << s[i];
		}
		cout << endl;
	} else {
		cout << "NOT UNIQUE" << endl;
	}
	return 0;
}

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