Submission #535884

#	Time	Username	Problem	Language	Result	Execution time	Memory
535884		daisy	Three Friends (BOI14_friends)	C++17	100 / 100	92 ms	36668 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,hr=-1000000;
    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<s.size();i++)
    {
        h[i]=(h[i-1]+(st[i]*(s[i]-'A'))%mod)%mod;//cout<<"( "<<i<<" "<<h[i]<<" "<<st[i]<<" "<<s[i]<<" "<<s[i]-'A'<<endl;

    }
    long long brd=n/2,r,re,in=-1;

    long long s1=faststep(base,mod-2),s2=faststep(st[brd+1],mod-2),s3=faststep(st[brd],mod-2);

    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)*s1)%mod;r%=mod;//cout<<"* "<<((h[brd]-h[i]+mod)%mod)<<" "<<h[i]<<endl;
            re=(((h[n-1]-h[brd]+mod)%mod)*s2)%mod;
        }
        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;r%=mod;

            re=h[brd-1];
        }
        if(r==re)
        {
            if(in!=-1 && hr!=r) {cout<<"NOT UNIQUE"<<endl;return 0;}
            in=i;hr=r;
        }
    }
    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;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=1;i<s.size();i++)
      |                 ~^~~~~~~~~

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