제출 #748453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748453		mariowong	세 명의 친구들 (BOI14_friends)	C++14	100 / 100	61 ms	22476 KiB

friends

#include <bits/stdc++.h>
const long long hmod=1e9+7;
using namespace std;
 
int n,pos1,pos2,ct,ans;
string s,t,r,anss;
bool ok;
long long h[2000005];
map <long long,bool> m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> s;
	if (n%2 == 0){
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	for (int i=1;i<=n/2;i++) t+=s[i];
	for (int i=n/2+1;i<n;i++) r+=s[i];
	for (int i=0;i<n/2;i++){
		if (t[i] == r[i]) ct++;
	}
	long long hnum=0,b=0,now=1;
	for (int i=1;i<n/2;i++) hnum=(hnum*26+s[i]-'A')%hmod;
	for (int i=0;i<n/2;i++){
		h[i]=(hnum+b)%hmod;
		hnum-=(s[i+1]-'A')*now; hnum%=hmod;
		hnum+=hmod; hnum%=hmod;
		b=(b+(s[i]-'A')*now)%hmod;
		now*=26; now%=26;
	}
	for (int i=n/2;i<n;i++) h[i]=h[i-1];
	for (int i=0;i<n;i++){
		if (ct == n/2){
			if (!m[h[i]]) ans++;
			if (!m[h[i]]) anss=t;
			m[h[i]]=true;
			if (ans > 1){
				ok=true;
				break;	
			} 
		}
		if (pos1 != n/2){
			if (t[pos1] == r[pos1]) ct--;
			t[pos1]=s[i];
			if (t[pos1] == r[pos1]) ct++;
			pos1++;
		}
		else
		{
			if (t[pos2] == r[pos2]) ct--;
			r[pos2]=s[i];
			if (t[pos2] == r[pos2]) ct++;
			pos2++;
		}
	///	cout << ans << "\n";
	}
	if (ct == n/2){
		if (!m[h[n-1]]) ans++;
		if (!m[h[n-1]]) anss=t;
		m[h[n-1]]=true;
		if (ans > 1) ok=true;
	}
	if (ok) cout << "NOT UNIQUE\n";
	else if (ans == 0) cout << "NOT POSSIBLE\n";
	else cout << anss << "\n";
	return 0;
}	

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