Submission #226426

#	Time	Username	Problem	Language	Result	Execution time	Memory
226426		MKopchev	Three Friends (BOI14_friends)	C++14	0 / 100	92 ms	20248 KiB

friends

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e6+42,base=29,mod=1e9+7;

string inp;

string outp;

int n,sz;

int st[nmax],pref[nmax];

set<int> seen;

int ask(int l,int r)
{
    if(l>r)return 0;

    long long help=pref[r];

    long long sub=0;
    if(l)sub=pref[l-1];

    sub=sub*st[r-l+1]%mod;

    //cout<<"ask "<<l<<" "<<r<<" -> "<<((help-sub)%mod+mod)%mod<<endl;

    return ((help-sub)%mod+mod)%mod;
}
void pick(int l,int r)
{
    int now=ask(l,r);

    if(seen.count(now))return;

    seen.insert(now);

    if(seen.size()>=2)
    {
        cout<<"NOT UNIQUE"<<endl;
        exit(0);
    }

    for(int i=l;i<=r;i++)
        outp.push_back(inp[i]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    cin>>sz;
    cin>>inp;

    n=(sz-1)/2;

    pref[0]=inp[0]-'A';

    for(int i=1;i<sz;i++)
        pref[i]=(1LL*pref[i-1]*base+inp[i]-'A')%mod;

    st[0]=1;
    for(int i=1;i<sz;i++)st[i]=1LL*st[i-1]*base%mod;

    //in the first half
    for(int i=0;i<=n;i++)
    {
        //cut i-th
        long long part1=ask(0,i-1)*st[n-i];

        long long part2=ask(i+1,n);

        part1=(part1+part2)%mod;

        if(part1==ask(n+1,sz-1))
            pick(n+1,sz-1);
    }
    //in the second half
    for(int i=n;i<sz;i++)
    {
        //cut i-th
        long long part1=ask(n,i-1)*st[sz-1-i];

        long long part2=ask(i+1,sz-1);

        part1=(part1+part2)%mod;

        if(part1==ask(0,n-1))
            pick(0,n-1);
    }

    if(outp.size())cout<<outp<<endl;
    else cout<<"NOT POSSIBLE"<<endl;
    return 0;
}

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