Submission #226439

#	Time	Username	Problem	Language	Result	Execution time	Memory
226439		MKopchev	Three Friends (BOI14_friends)	C++14	100 / 100	189 ms	21904 KiB

friends

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

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;
}

bool been_0=0,been_n=0;

void pick(int l,int r)
{
    if(l==0&&been_0)return;
    if(l==n+1&&been_n)return;

    string help="";

    for(int i=l;i<=r;i++)
        help.push_back(inp[i]);

    if(outp.size())
    {
        if(help!=outp)
        {
            cout<<"NOT UNIQUE"<<endl;
            exit(0);
        }
    }

    outp=help;

    if(l==0)been_0=1;
    if(l==n+1)been_n=1;
}
int main()
{
    scanf("%i",&sz);

    if(sz%2==0)
    {
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }

    for(int i=0;i<sz;i++)
    {
        char c=getchar();
        while('A'>c||c>'Z')c=getchar();
        inp.push_back(c);
    }

    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;

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

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

        part1=(part1+part2)%mod;

        //cout<<part1<<" "<<ask(n+1,sz-1)<<endl;

        if(part1==mem)
            pick(n+1,sz-1);
    }

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

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

        part1=(part1+part2)%mod;

        //cout<<part1<<" "<<ask(0,n-1)<<endl;

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

    if(outp.size())
    {
        for(auto k:outp)
            printf("%c",k);
        printf("\n");
    }
    else cout<<"NOT POSSIBLE"<<endl;
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&sz);
     ~~~~~^~~~~~~~~~

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