Submission #956532

#	Time	Username	Problem	Language	Result	Execution time	Memory
956532		ezzzay	Three Friends (BOI14_friends)	C++14	100 / 100	38 ms	6224 KiB

friends

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
#define pb push_back
#define ff first
#define ss second
const int N=1e5+5;
vector<int>ans;
 void fun(int n){
     if(n%2==0){
		cout<<"NOT POSSIBLE";
		return ;
	}
	string s;
	set<string>st;
	cin>>s;
	for(int i=0;i<n;i++){
		string tmp;
		for(int j=0;j<n;j++){
			if(i==j)continue;
			tmp+=s[j];
		}
		if(tmp.substr(0,n/2)==tmp.substr(n/2,n/2)){
			st.insert(tmp.substr(0,n/2));
		}
	}
	if(st.size()>1){
		cout<<"NOT UNIQUE";
	}
	else if(st.size()==0){
		cout<<"NOT POSSIBLE";
	}
	else cout<< *st.begin();
 }
signed main(){
	int n;
	cin>>n;
	if(n<=2001){
	    fun(n);
	    return 0;
	}
	string s;
	set<char>st;
	cin>>s;
	if(n%2==0){
		cout<<"NOT POSSIBLE";
		return 0;
	}
	int l1=0;
	int r1=n/2+1;
	int cnt1=0;
	int u1=0;
	int e1=0;
	while(cnt1!=n/2){
	    if(s[l1]!=s[r1]){
	        l1++;
	        e1=1;
	        u1++;
	        if(u1==2){
	            e1=0;
	            break;
	        }
	    }
	    l1++;
	    r1++;
	    cnt1++;
	}
	int p1=1;
	if(u1==2 and e1==0){
	    p1=0;
	}
	
	reverse(s.begin(),s.end());
	
	int l2=0;
	int r2=n/2+1;
	int cnt2=0;
	int u2=0;
	int e2=0;
	while(cnt2!=n/2){
	    if(s[l2]!=s[r2]){
	        l2++;
	        e2=1;
	        u2++;
	        if(u2==2){
	            e2=0;
	            break;
	        }
	    }
	    l2++;
	    r2++;
	    cnt2++;
	}
	int p2=1;
	if(e1 and e2){
	    cout<<"NOT UNIQUE";
	    return 0;
	}
	
	
	
	
	if(u1==2 and u2==2){
	    cout<<"NOT POSSIBLE";
	    return 0;
	}
	
	
	reverse(s.begin(),s.end());
	if(p1){
	    cout<<s.substr(n/2+1,n/2);
	    return 0;
	}
	if(p2){
	    cout<<s.substr(0,n/2);
	    return 0;
	}
	
	
}

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