제출 #413792

#제출 시각아이디문제언어결과실행 시간메모리
413792BlagojceThree Friends (BOI14_friends)C++11
0 / 100
75 ms36452 KiB
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
  
const int mxn = 2e6+5;

const ll A = 911382323;
const ll B = 972663749;

mt19937 _rand(time(NULL));
clock_t z;

ll p[mxn];
ll h[mxn];


int n;
string s;

ll range_hash(int l, int r){
	ll ret = h[r];
	if(l > 0){
		ret -= (h[l-1]*p[r-l+1])%B;
		if(ret < 0) ret += B;
	}
	return ret;
}


void solve(){
	
	
	cin >> n;
	cin >> s;
	n = (int)s.size();
	
	
	if(n % 2 == 0){
		cout<<"NOT POSSIBLE"<<endl;
		return;
	}
	
	h[0] = (int)s[0];
	fr(i, 1, n){
		h[i] = (h[i-1]*A + (int)s[i]) % B;
	}
	vector<int> pos;
	fr(i, 0, n){
		if(i < n/2){
			int l1 = 0;
			int r1 = i-1;
			
			int l2 = i+1;
			int r2 = n/2;
			
			bool same = true;
			if(l1 <= r1){
				int lp = n/2+1;
				int rp = n/2+1 + r1-l1;
				same &= range_hash(l1, r1) == range_hash(lp, rp);
			}
			if(l2 <= r2){
				int rp = n-1;
				int lp = n-1 - r2+l2;
				same &= range_hash(l2, r2) == range_hash(lp, rp);
			}
			if(same){
				pos.pb(i);
			}
		}
		else if(i == n/2){
		
			if(range_hash(0, n/2-1) == range_hash(n/2+1, n-1)){
				pos.pb(i);
			}
		}
		else{
			int l1 = n/2;
			int r1 = i-1;
			
			int l2 = i+1;
			int r2 = n-1;
			
			bool same = true;
			if(l1 <= r1){
				int lp = 0;
				int rp = r1-l1;
				

				same &= range_hash(l1, r1) == range_hash(lp, rp);
			}
			if(l2 <= r2){
				int lp = r1-l1+1;
				int rp = r1-l1+1 + r2-l2;
				same &= range_hash(l2, r2) == range_hash(lp, rp);
				
			}
			if(same){
				pos.pb(i);
			}
		}
	}
	if((int)pos.size() == 0){
		cout<<"NOT POSSIBLE"<<endl;
	}
	else if((int)pos.size() > 1){
		cout<<"NOT UNIQUE"<<endl;
	}
	else{
		string ans = "";
		fr(i, 0, n){
			if(i == pos[0]) continue;
			ans += s[i];
			if((int)ans.size() == (n-1)/2){
				break;
			}
		}
		cout<<ans<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	p[0] = 1;
	fr(i, 1, mxn){
		p[i] = (p[i-1]*A)%B;
	}
	solve();
	/*while(1){
		cin >> s;
		s = s + s;
		int pos = _rand()%(int)s.size();
		
		s.insert(s.begin()+pos, 'X');
		solve();
	
	}*/
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...