제출 #1362630

#제출 시각아이디문제언어결과실행 시간메모리
1362630archnerd_ishaan세 명의 친구들 (BOI14_friends)C++20
0 / 100
61 ms70792 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
#define pb push_back

#define A 911382323LL
#define B 1000000007LL
#define C 972663749LL
#define D 1000000009LL
#define mp make_pair

vll h1, p1, h2, p2;

void hinit(string s, int n) {
	h1.assign(n, 0);
	p1.assign(n, 0);
	h2.assign(n, 0);
	p2.assign(n, 0);
	h1[0] = s[0];
	p1[0] = 1;
	h2[0] = s[0];
	p2[0] = 1;
	for (int i = 1; i < n; i++) {
		h1[i] = (h1[i-1]*A+s[i])%B;
		p1[i] = (p1[i-1]*A)%B;
		h2[i] = (h2[i-1]*C+s[i])%D;
		p2[i] = (p2[i-1]*C)%D;
	}
}

pair<ll,ll> sbsh(int a, int b) {
	if (b<a||min(a,b)<0||max(a,b)>=h1.size()) return mp(0,0);
	return (a==0)?mp(h1[b], h2[b]):mp((h1[b]-(h1[a-1]*p1[b-a+1])%B+B)%B,(h2[b]-(h2[a-1]*p2[b-a+1])%D+D)%D);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, i;
	cin >> n;
	string s;
	cin >> s;
	hinit(s,n);
	unordered_map<int,int> cnt;
	for (i = 0; i < n; i++) cnt[s[i]]++;
	int ov;
	for (auto i : cnt) {
		if (i.second%2==1) {
			ov = i.first;
			break;
		}
	}
	int d = 0;
	string c;
	pair<ll,ll> h;
	for (i = 0; i < n; i++) {
		if (s[i] == ov) {
			pair<ll,ll> lh, rh, c1, c2;
			if (i == n/2) {
				lh = sbsh(0,n/2-1);
				rh = sbsh(n/2+1,n-1);
			}
			else if (i < n/2) {
				c1 = sbsh(0,i-1);
				c2 = sbsh(i+1,n/2);
				lh = mp((c1.first*p1[n/2-i]+c2.first)%B,(c1.second*p2[n/2-i]+c2.second)%D);
				rh = sbsh(n/2+1,n-1);
			}
			else {
				lh = sbsh(0,n/2-1);
				c1 = sbsh(n/2,i-1);
				c2 = sbsh(i+1,n-1);
				rh = mp((c1.first*p1[n-i-1]+c2.first)%B,(c1.second*p2[n-i-1]+c2.second)%D);
			}
			if (lh==rh) {
				if (d==1&&lh!=h) {
					cout << "NOT UNIQUE" << endl;
					d = 2;
					break;
				}
				if (d==0) {
					string t;
					for (int j = 0; j < n; j++) if (j!=i) t += s[j];
					for (int j = 0; j < n/2; j++) c += t[j];
				}
				d = 1;
			}
		}
	}
	if (d==0) cout << "NOT POSSIBLE" << endl;
	else if (d==1) cout << c << endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…