Submission #535769

#	Time	Username	Problem	Language	Result	Execution time	Memory
535769		daisy	Three Friends (BOI14_friends)	C++17	0 / 100	147 ms	97752 KiB

friends

#include<iostream>
#define endl '\n'
using namespace std;
const long long mod=1000000007,base=27,mod2=113963,base2=37,mod3=1000000009,base3=7;
long long h[2000005],st[2000005],h2[2000005],st2[2000005],h3[2000005],st3[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;
}
long long faststep3(long long n,long long st)
{
    if(st==0) return 1;
    if(st==1) return n;

    if(st%2==0)
    {
        long long r=faststep3(n,st/2);
        return r*r%mod3;
    }
    else
        return faststep3(n,st-1)*n%mod3;
}
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;st3[0]=1;
    for(int i=1;i<=n;i++)
    {
        st[i]=(st[i-1]*base)%mod;
        st2[i]=(st2[i-1]*base2)%mod2;
        st3[i]=(st3[i-1]*base3)%mod3;
    }
    h[0]=(s[0]-'A');h2[0]=(s[0]-'A');h3[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;
        h3[i]=(h3[i-1]+st3[i]*(s[i]-'A'))%mod3;
    }
    long long brd=n/2,r,re,r2,re2,r3,re3,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);
    long long s31=faststep3(base3,mod3-2),s32=faststep3(st3[brd+1],mod3-2),s33=faststep3(st3[brd],mod3-2);

    for(int i=0;i<n;i++)
    {
        r=0;re=0;r2=0;re2=0;r3=0;re3=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;

            if(i>0) r3+=h3[i-1];
            r3+=((h3[brd]-h3[i]+mod3)%mod3*s31)%mod3;r3%=mod3;
            re3=(((h3[n-1]-h3[brd]+mod3)%mod3)*s32)%mod3;
        }
        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];

            r3=((h3[i-1]-h3[brd-1]+mod3)%mod3)*s33%mod3;
            r3+=((h3[n-1]-h3[i]+mod3)%mod3)*s32%mod3;

            re3=h3[brd-1];
        }
       // cout<<i<<" "<<r<<" "<<re<<" "<<r2<<" "<<re2<<endl;
        if(r==re && r2==re2 && r3==re3)
        {
            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