Submission #391039

#	Time	Username	Problem	Language	Result	Execution time	Memory
391039		shahriarkhan	Three Friends (BOI14_friends)	C++14	100 / 100	392 ms	44448 KiB

friends

#include<bits/stdc++.h>
using namespace std ;

const int mx = 3e6 ;

int a[mx] , n ;

long long val[mx] , store[mx][2] , pre[2] ;

string s ;

long long gcd(long long a , long long b , long long &x , long long &y)
{
    if(!a)
    {
        x = 0 , y = 1 ;
        return b ;
    }
    long long x1 , y1 ;
    long long d = gcd(b%a,a,x1,y1) ;
    x = y1 - (b/a)*x1 ;
    y = x1 ;
    return d ;
}

long long modinverse(long long a , long long m)
{
    long long x , y ;
    long long g = gcd(a,m,x,y) ;
    return (x%m + m)%m ;
}

void f(long long mod , int stat)
{
    long long P = 1 , first = 0 , second = 0 , c_first = 0 , c_second = 0 , tot = 0 , div = modinverse(31,mod) ;
    //precompute 0..(n/2)
    for(int i = 0 ; i <= (n/2) ; ++i)
    {
        long long c_cnt = (s[i] - 'A' + 1) ;
        first = (first + (c_cnt*P)%mod)%mod ;
        P = (P*31LL)%mod ;
    }
    //precompute (n/2)..(n-1)
    P = 1 ;
    for(int i = (n/2) ; i < n ; ++i)
    {
        long long c_cnt = (s[i] - 'A' + 1) ;
        second = (second + (c_cnt*P)%mod)%mod ;
        P = (P*31LL)%mod ;
    }
    //precompute 0..((n/2) - 1)
    P = 1 ;
    for(int i = 0 ; i < (n/2) ; ++i)
    {
        long long c_cnt = (s[i] - 'A' + 1) ;
        c_first = (c_first + (c_cnt*P)%mod)%mod ;
        P = (P*31LL)%mod ;
    }
    //precompute (n/2 + 1)..(n-1)
    P = 1 ;
    for(int i = (n/2) + 1 ; i < n ; ++i)
    {
        long long c_cnt = (s[i] - 'A' + 1) ;
        c_second = (c_second + (c_cnt*P)%mod)%mod ;
        P = (P*31LL)%mod ;
    }
    //check if it is in the range (0...((n/2)-1))
    P = 1 ;
    for(int i = 0 ; i < (n/2) ; ++i)
    {
        long long c_cnt = (s[i] - 'A' + 1) ;
        tot = (tot + (c_cnt*P)%mod)%mod ;
        long long cur = (((first-tot+mod)%mod)*div)%mod ;
        cur = (cur + tot - (c_cnt*P)%mod + mod)%mod ;
        store[i][stat] = cur ;
        if(cur==c_second) a[i] &= 1 ;
        else a[i] = 0 ;
        P = (P*31LL)%mod ;
    }
    //check if it is in the range ((n/2)...(n-1))
    tot = 0 , P = 1 ;
    for(int i = n/2 ; i < n ; ++i)
    {
        long long c_cnt = (s[i] - 'A' + 1) ;
        tot = (tot + (c_cnt*P)%mod)%mod ;
        long long cur = (((second-tot+mod)%mod)*div)%mod ;
        cur = (cur + tot - (c_cnt*P)%mod + mod)%mod ;
        store[i][stat] = cur ;
        if(cur==c_first) a[i] &= 1 ;
        else a[i] = 0 ;
        P = (P*31LL)%mod ;
    }
}

int main()
{
    int ans = -1 , cnt = 0 ;
    scanf("%d",&n) ;
    cin>>s ;
    if(!(n&1))
    {
        puts("NOT POSSIBLE") ;
        return 0 ;
    }
    for(int i = 0 ; i < n ; ++i) a[i] = 1 ;
    long long cur = 1e9 + 7 ;
    f(cur,0) ;
    cur = 1e9 + 9 ;
    f(cur,1) ;
    pre[0] = -1 , pre[1] = -1 ;
    for(int i = 0 ; i < n ; ++i)
    {
        if(a[i])
        {
            if(pre[0]>=0)
            {
                if(pre[0]!=store[i][0])
                {
                    puts("NOT UNIQUE") ;
                    return 0 ;
                }
            }
            pre[0] = store[i][0] ;
            ans = i ;
        }
        cnt += a[i] ;
    }
    if(!cnt)
    {
        puts("NOT POSSIBLE") ;
    }
    else
    {
        for(int i = 0 ; i < (n/2) + (ans<(n/2)) ; ++i)
        {
            if(i==ans) continue ;
            cout<<s[i] ;
        }
        cout<<endl ;
    }
    return 0 ;
}

Compilation message (stderr)

friends.cpp: In function 'long long int modinverse(long long int, long long int)':
friends.cpp:29:15: warning: unused variable 'g' [-Wunused-variable]
   29 |     long long g = gcd(a,m,x,y) ;
      |               ^
friends.cpp: In function 'int main()':
friends.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~

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