oj.uz

Submission #310918

# Submission time Handle Problem Language Result Execution time Memory
310918 2020-10-08T13:49:18 Z mohamedsobhi777 Three Friends (BOI14_friends) C++14
100 / 100
 26 ms 15096 KB 
#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

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

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 0 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 0 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 0 ms 384 KB Output is correct
35 Correct 1 ms 328 KB Output is correct
36 Correct 0 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 0 ms 384 KB Output is correct
39 Correct 0 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 0 ms 384 KB Output is correct
42 Correct 0 ms 384 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Correct 0 ms 384 KB Output is correct
45 Correct 0 ms 384 KB Output is correct
46 Correct 1 ms 384 KB Output is correct
47 Correct 0 ms 384 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 0 ms 384 KB Output is correct
50 Correct 0 ms 384 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 0 ms 384 KB Output is correct
53 Correct 1 ms 384 KB Output is correct
54 Correct 1 ms 384 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14208 KB Output is correct
2 Correct 24 ms 14072 KB Output is correct
3 Correct 24 ms 14080 KB Output is correct
4 Correct 24 ms 14080 KB Output is correct
5 Correct 26 ms 15096 KB Output is correct
6 Correct 12 ms 10276 KB Output is correct
7 Correct 15 ms 12196 KB Output is correct
8 Correct 22 ms 12740 KB Output is correct
9 Correct 22 ms 12740 KB Output is correct
10 Correct 24 ms 13628 KB Output is correct
11 Correct 17 ms 10276 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 288 KB Output is correct
32 Correct 0 ms 384 KB Output is correct
33 Correct 0 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 0 ms 384 KB Output is correct
36 Correct 0 ms 384 KB Output is correct
37 Correct 0 ms 384 KB Output is correct
38 Correct 0 ms 384 KB Output is correct
39 Correct 1 ms 384 KB Output is correct
40 Correct 0 ms 384 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 1 ms 384 KB Output is correct
43 Correct 0 ms 384 KB Output is correct
44 Correct 1 ms 384 KB Output is correct
45 Correct 0 ms 384 KB Output is correct
46 Correct 1 ms 384 KB Output is correct
47 Correct 0 ms 384 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 0 ms 384 KB Output is correct
50 Correct 1 ms 384 KB Output is correct
51 Correct 0 ms 384 KB Output is correct
52 Correct 0 ms 384 KB Output is correct
53 Correct 0 ms 384 KB Output is correct
54 Correct 1 ms 384 KB Output is correct