Submission #391028

#	Time	Username	Problem	Language	Result	Execution time	Memory
391028		shahriarkhan	Three Friends (BOI14_friends)	C++14	0 / 100	342 ms	11204 KiB

friends

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

const int mx = 3e6 ;

int a[mx] , n ;

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)
{
    long long P = 1 , first = 0 , second = 0 , c_first = 0 , c_second = 0 , tot = 0 , div = modinverse(31,mod) ;
    for(int i = 0 ; i <= (n/2) ; ++i)
    {
        if(i==(n/2)) c_first = first ;
        first = (first + ((s[i]-'A'+1)*P)%mod)%mod ;
        P = (P*31LL)%mod ;
    }
    P = 1 ;
    for(int i = (n/2) ; i < n ; ++i)
    {
        second = (second + ((s[i]-'A'+1)*P)%mod)%mod ;
        P = (P*31LL)%mod ;
    }
    P = 1 ;
    for(int i = (n/2) + 1 ; i < n ; ++i)
    {
        c_second = (c_second + ((s[i]-'A'+1)*P)%mod)%mod ;
        P = (P*31LL)%mod ;
    }
    P = 1 ;
    for(int i = 0 ; i < (n/2) ; ++i)
    {
        tot = (tot + ((s[i]-'A'+1)*P)%mod)%mod ;
        long long cur = (tot - ((s[i]-'A'+1)*P)%mod + (((first-tot+mod)%mod)*div)%mod + mod)%mod ;
        if(cur==c_second) a[i] &= 1 ;
        else a[i] = 0 ;
        P = (P*31LL)%mod ;
    }
    tot = 0 , P = 1 ;
    for(int i = n/2 ; i < n ; ++i)
    {
        tot = (tot + ((s[i]-'A'+1)*P)%mod)%mod ;
        long long cur = (tot - ((s[i]-'A'+1)*P)%mod + (((second - tot+mod)*div)%mod + mod))%mod ;
        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) ;
    cur = 1e9 + 9 ;
    f(cur) ;
    for(int i = 0 ; i < n ; ++i)
    {
        if(a[i]) ans = i ;
        cnt += a[i] ;
    }
    if(!cnt)
    {
        puts("NOT POSSIBLE") ;
    }
    else if(cnt==1)
    {
        for(int i = 0 ; i < (n/2) + (ans<(n/2)) ; ++i)
        {
            if(i==ans) continue ;
            cout<<s[i] ;
        }
        cout<<endl ;
    }
    else
    {
        puts("NOT UNIQUE") ;
    }
    return 0 ;
}

Compilation message (stderr)

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

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