Submission #535686

#	Time	Username	Problem	Language	Result	Execution time	Memory
535686		daisy	Three Friends (BOI14_friends)	C++17	0 / 100	1020 ms	36656 KiB

friends

#include<iostream>
#define endl '\n'
using namespace std;
const long long mod=1000000007,base=27;
long long h[2000005],st[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;
}
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;
    for(int i=1;i<=n;i++)
        st[i]=(st[i-1]*base)%mod;


    h[0]=(s[0]-'A');
    for(int i=1;i<n;i++)
    {
        h[i]=(h[i-1]+st[i]*(s[i]-'A'))%mod;
    }
    long long brd=n/2,r,re,in=-1;


    for(int i=0;i<n;i++)
    {
        r=0;re=0;
        if(i<=brd)
        {
            if(i>0) r+=h[i-1];
            r+=((h[brd]-h[i]+mod)%mod*faststep(base,mod-2))%mod;r%=mod;
            re=(((h[n-1]-h[brd]+mod)%mod)*faststep(st[brd+1],mod-2))%mod;
        }
        else if(i>brd)
        {
            r=((h[i-1]-h[brd-1]+mod)%mod)*faststep(st[brd],mod-2)%mod;
            r+=((h[n-1]-h[i]+mod)%mod)*faststep(st[brd+1],mod-2)%mod;

            re=h[brd-1];
        }
        if(r==re)
        {
            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