Submission #535690

#	Time	Username	Problem	Language	Result	Execution time	Memory
535690		daisy	Three Friends (BOI14_friends)	C++17	0 / 100	72 ms	64908 KiB

friends

#include<iostream>
#define endl '\n'
using namespace std;
const long long mod=1000000007,base=27,mod2=100000000069,base2=37;
long long h[2000005],st[2000005],h2[2000005],st2[2000005];
long long faststep(long long n,long long st)
{
    if(st==0) return 1;
    if(st==1) return n;

    if(st%2==0)
    {
        long long r=faststep(n,st/2);
        return r*r%mod;
    }
    else
        return faststep(n,st-1)*n%mod;
}
long long faststep2(long long n,long long st)
{
    if(st==0) return 1;
    if(st==1) return n;

    if(st%2==0)
    {
        long long r=faststep2(n,st/2);
        return r*r%mod2;
    }
    else
        return faststep2(n,st-1)*n%mod2;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n;
    string s;
    cin>>n;
    cin>>s;
    if(n%2==0)
    {
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }
    st[0]=1;st2[0]=1;
    for(int i=1;i<=n;i++)
    {
        st[i]=(st[i-1]*base)%mod;
        st2[i]=(st2[i-1]*base2)%mod2;
    }
    h[0]=(s[0]-'A');h2[0]=(s[0]-'A');
    for(int i=1;i<n;i++)
    {
        h[i]=(h[i-1]+st[i]*(s[i]-'A'))%mod;
        h2[i]=(h2[i-1]+st2[i]*(s[i]-'A'))%mod2;
    }
    long long brd=n/2,r,re,r2,re2,in=-1;

    long long s1=faststep(base,mod-2),s2=faststep(st[brd+1],mod-2),s3=faststep(st[brd],mod-2);
    long long s21=faststep2(base2,mod2-2),s22=faststep2(st2[brd+1],mod2-2),s23=faststep2(st2[brd],mod2-2);

    for(int i=0;i<n;i++)
    {
        r=0;re=0;r2=0;re2=0;
        if(i<=brd)
        {
            if(i>0) r+=h[i-1];
            r+=((h[brd]-h[i]+mod)%mod*s1)%mod;r%=mod;
            re=(((h[n-1]-h[brd]+mod)%mod)*s2)%mod;

            if(i>0) r2+=h2[i-1];
            r2+=((h2[brd]-h2[i]+mod2)%mod2*s21)%mod2;r2%=mod2;
            re2=(((h2[n-1]-h2[brd]+mod2)%mod2)*s22)%mod2;
        }
        else if(i>brd)
        {
            r=((h[i-1]-h[brd-1]+mod)%mod)*s3%mod;
            r+=((h[n-1]-h[i]+mod)%mod)*s2%mod;

            re=h[brd-1];

            r2=((h2[i-1]-h2[brd-1]+mod2)%mod2)*s23%mod2;
            r2+=((h2[n-1]-h2[i]+mod2)%mod2)*s22%mod2;

            re2=h2[brd-1];
        }
       // cout<<i<<" "<<r<<" "<<re<<" "<<r2<<" "<<re2<<endl;
        if(r==re && r2==re2)
        {
            if(in!=-1) {cout<<"NOT UNIQUE"<<endl;return 0;}
            in=i;
        }
    }
    if(in==-1)
    {
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }

    int brb=0;
    for(int i=0;brb<brd;i++)
    {
        if(i==in) continue;
        brb++;
        cout<<s[i];
    }
cout<<endl;
}

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