Submission #418790

#	Time	Username	Problem	Language	Result	Execution time	Memory
418790		VladM	Three Friends (BOI14_friends)	C++14	0 / 100	248 ms	67044 KiB

friends

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<ll, ull> plu;

int get_num(char c)
{
    return c-'A'+1;
}

struct polyhash
{
    ll base=31;
    ll mod=1e9+7;
    vector<ll> pow1;
    vector<ull> pow2;
    vector<ll> pref1;
    vector<ull> pref2;
    void make_hash(string s)
    {
        ll len=s.length();
        pow1.resize(len+1);
        pow1[0]=1;
        pow2.resize(len+1);
        pow2[0]=1;
        for(int i=1; i<=len; i++)
        {
            pow1[i]=(pow1[i-1]*base)%mod;
            pow2[i]=pow2[i-1]*base;
        }
        pref1.resize(len);
        pref2.resize(len);
        pref1[0]=get_num(s[0]);
        pref2[0]=get_num(s[0]);
        for(int i=1; i<len; i++)
        {
            pref1[i]=(pref1[i-1]*base+get_num(s[i]))%mod;
            pref2[i]=pref2[i-1]*base+get_num(s[i]);
        }
    }
    plu get_hash(ll L, ll R)
    {
        ll len=R-L+1;
        if(L==0)
        {
            return {pref1[R], pref2[R]};
        }
        ll h1=(pref1[R]-(pref1[L-1]*pow1[len])%mod)%mod;
        if(h1<0) h1+=mod;
        ull h2=pref2[R]-pref2[L-1]*pow2[len];
        return {h1, h2};
    }
    plu reun(ll L1, ll R1, ll L2, ll R2)
    {
        plu hash1=get_hash(L1, R1);
        plu hash2=get_hash(L2, R2);
        ll len=R2-L2+1;
        ll h1=((hash1.first*pow1[len])%mod+hash2.first)%mod;
        if(h1<0) h1+=mod;
        ull h2=hash1.second*pow2[len]+hash2.second;
        return {h1, h2};
    }
};

polyhash h;

string s;

ll n, it, cnt;

plu hash1, hash2, ans;

int main()
{
    cin>>n;
    cin>>s;
    h.make_hash(s);
    if(n%2==0)
    {
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }
    hash1=h.get_hash(0, n/2-1);
    hash2=h.get_hash(n/2+1, n-1);
    if(hash1==hash2)
    {
        ans=hash1;
        it=0;
        cnt=1;
    }
    for(int i=0; i<n/2; i++)
    {
        if(i==0)
        {
            hash1=h.get_hash(1, n/2);
        }
        else hash1=h.reun(0, i-1, i+1, n/2);
        if(hash1==hash2)
        {
            if(hash1!=ans) cnt++;
            it=1;
        }
    }
    hash1=h.get_hash(0, n/2-1);
    for(int i=n/2+1; i<n; i++)
    {
        if(i==n-1)
        {
            hash2=h.get_hash(n/2, i-1);
        }
        else
        {
            hash2=h.reun(n/2, i-1, i+1, n-1);
        }
        if(hash1==hash2)
        {
            if(ans!=hash1) cnt++;
            it=0;
        }
    }
    if(cnt==0)
    {
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }
    if(cnt>1)
    {
        cout<<"NOT UNIQUE"<<endl;
        return 0;
    }
    if(it==0)
    {
        for(int i=0; i<n/2; i++) cout<<s[i];
        cout<<endl;
        return 0;
    }
    for(int i=n/2+1; i<n; i++) cout<<s[i];
    cout<<endl;
    return 0;
}

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