Submission #1190343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190343		AlgorithmWarrior	Three Friends (BOI14_friends)	C++20	100 / 100	135 ms	18796 KiB

friends

#include <bits/stdc++.h>

using namespace std;

int const MOD=1e9+7;
int const BASE=31;
int const MAX=2000005;
int n;
char sir[MAX];
int hashes[MAX];
int bpow[MAX];
int ans_hash,ans_id;

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>sir[i];
}

void precalc(){
    int i;
    bpow[0]=1;
    for(i=1;i<MAX;++i)
        bpow[i]=1LL*BASE*bpow[i-1]%MOD;
    for(i=1;i<=n;++i)
        hashes[i]=(1LL*BASE*hashes[i-1]%MOD+sir[i]-'A'+1)%MOD;
}

int hash_intv(int l,int r){
    return (hashes[r]-1LL*hashes[l-1]*bpow[r-l+1]%MOD+MOD)%MOD;
}

int hash_2intv(int l1,int r1,int l2,int r2){
    return (1LL*hash_intv(l1,r1)*bpow[r2-l2+1]%MOD+hash_intv(l2,r2))%MOD;
}

void solve(){
    if(n%2==0)
        return;
    int i;
    for(i=1;i<=n;++i){
        int hsh1,hsh2;
        if(i<=n/2+1){
            hsh1=hash_2intv(1,i-1,i+1,n/2+1);
            hsh2=hash_intv(n/2+2,n);
        }
        else{
            hsh1=hash_intv(1,n/2);
            hsh2=hash_2intv(n/2+1,i-1,i+1,n);
        }
        if(hsh1==hsh2){
            if(!ans_hash){
                ans_hash=hsh1;
                ans_id=i;
            }
            else
                if(ans_hash!=hsh1)
                    ans_id=0;
        }
    }
}

void answer(){
    if(ans_id){
        int i;
        for(i=1;i<=n/2+(ans_id<=n/2);++i)
            if(i!=ans_id)
                cout<<sir[i];
    }
    else{
        if(ans_hash)
            cout<<"NOT UNIQUE";
        else
            cout<<"NOT POSSIBLE";
    }
}

int main()
{
    read();
    precalc();
    solve();
    answer();
    return 0;
}

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