Submission #310918

#	Time	Username	Problem	Language	Result	Execution time	Memory
310918		mohamedsobhi777	Three Friends (BOI14_friends)	C++14	100 / 100	26 ms	15096 KiB

friends

#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 = 2e6 + 7 , mod = 1e9 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n ; 
string s; 
int answer = 0 ; 

int pref1[N] , pref2[N] ; 

inline bool good1(int l , int r){if(l>r)return 1; return  pref1[r] - (l ? pref1[l-1] : 0) == r - l + 1 ; }
inline bool good2(int l , int r){if(l>r)return 1; return pref2[r] - (l ? pref2[l-1] : 0) == r - l + 1; }

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        cin >> n; 
        cin >> s; 
        int ans = -1 ; 
        set<string> vec ; 

        for(int i = 0 ;i <= n / 2 ; ++ i){
                pref1[i] = (s[i] == s[i+n/2]) ; 
                pref2[i] = (s[i] == s[i+n/2+1]) ; 
                if(i){
                        pref1[i]+=pref1[i-1] ; 
                        pref2[i]+=pref2[i-1] ;
                }
        }

        if(n&1){
                if(s == string(n , s[0])){
                        return cout<< s.substr(0 , n / 2) , 0 ; 
                }
                for(int i = 0 ;i < n ; ++ i){
                        bool ok = 1 ; 
                        if(i>=n/2){
                                int j = i - n / 2; 
                                ok&=good1(0 , j - 1) ; 
                                ok&=good2(j,n/2-1) ;
                        }else{
                                ok&=good1(i + 1, n / 2) ; 
                                ok&=good2(0 , i - 1) ; 
                        }
                        if(ok){
                                string t = s ; 
                                t.erase(i , 1) ; 
                                vec.insert(t.substr(0 , n /2)) ; 
                        }
                }
                if(vec.size() == 1){
                        cout<< *vec.begin() ; 
                }else if(vec.size() > 1)
                        cout<<"NOT UNIQUE" ; 
                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. 
*/

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:41:13: warning: unused variable 'ans' [-Wunused-variable]
   41 |         int ans = -1 ;
      |             ^~~

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