Submission #310911

#TimeUsernameProblemLanguageResultExecution timeMemory
310911mohamedsobhi777Three Friends (BOI14_friends)C++14
0 / 100
1087 ms4388 KiB
#include<bits/stdc++.h>


#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 2e5 + 7 , mod = 1e9 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n ; 
string s; 
int answer = 0 ; 

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        cin >> n; 
        cin >> s; 
        int ans = -1 ; 
        if(n&1){
                for(int i = 0 ;i < n ; ++ i){
                        bool ok = 1 ; 
                        if(i>=n/2){
                                int j = i - n / 2; 
                                for(int k = 0 ; k < j ; ++ k){
                                        ok&=(s[k] == s[k+n/2]); 
                                }
                                for(int k = j ; k < n / 2 ; ++ k){
                                        ok&=(s[k] == s[k+n/2+1]) ; 
                                }
                        }else{
                                for(int j = 0 ;j <= n / 2 ; ++ j){
                                        if(i == j)continue ; 
                                        ok&=(s[j] == s[j + n / 2 + (j<i)]) ; 
                                }
                        }
                        if(ok){
                                if(~ans){
                                        cout<<"NOT UNIQUE" ; 
                                        return 0 ; 
                                }
                                ans = i ; 
                        }
                }
                if(~ans){
                        s.erase(ans , 1) ; 
                        cout<< s.substr(0 , n / 2) ; 
                }else cout<<"NOT POSSIBLE" ; 
        }
        else cout<<"NOT POSSIBLE" ; 
        return 0 ; 
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...