제출 #226434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226434		MKopchev	세 명의 친구들 (BOI14_friends)	C++14	35 / 100	1095 ms	23960 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&&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)been_n=1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    cin>>sz;
    cin>>inp;

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

    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=1LL*ask(0,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==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=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==ask(0,n-1))
            pick(0,n-1);
    }

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

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