Submission #413841

#	Time	Username	Problem	Language	Result	Execution time	Memory
413841		Blagojce	Three Friends (BOI14_friends)	C++11	100 / 100	82 ms	45420 KiB

friends

#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;
}
 
bool SAME(int l, int r, int x, int y){
	return (range_hash(l, r) == range_hash(x, y));
		
	
}
 
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 &= SAME(l1, r1, lp, rp);
			}
			if(l2 <= r2){
				int rp = n-1;
				int lp = n-1 - r2+l2;
				same &= SAME(l2, r2, 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 &= SAME(l1, r1, lp, rp);
			}
			if(l2 <= r2){
				int lp = r1-l1+1;
				int rp = r1-l1+1 + r2-l2;
				same &= SAME(l2, r2, lp, rp);
				
			}
			if(same){
				pos.pb(i);
			}
		}
	}
	if((int)pos.size() == 0){
		cout<<"NOT POSSIBLE"<<endl;
		return;
	}
	else if((int)pos.size() > 1){
		ll hs = -1;
		for(auto u : pos){
			
			ll ths;
			if(u < n/2){
				ths = range_hash(n/2+1, n-1);
			}
			else{
				ths = range_hash(0, n/2-1);
			}
			if(ths != hs){
				if(hs == -1){
					hs = ths;
				}
				else{
					cout<<"NOT UNIQUE"<<endl;
					return;
				}
			}
		}
		
	}
	
	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(){
	//freopen("untitled.in", "r",stdin);
	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();
}

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