Submission #361966

#	Time	Username	Problem	Language	Result	Execution time	Memory
361966		Ahmad_Hasan	Three Friends (BOI14_friends)	C++17	35 / 100	1083 ms	18192 KiB

friends

#include <bits/stdc++.h>
#define int long long
/**
     ||||||||||       |||||     |||||    ||||||||||
    |||||||||||||     |||||     |||||  |||||
   ||||     ||||||    |||||     |||||  |||||
  |||||||||||||||||   |||||||||||||||    ||||||||||
 |||||||||||||||||||  |||||||||||||||           |||||
 |||||         |||||  |||||     |||||           |||||
 |||||         |||||  |||||     |||||    ||||||||||
AHMED;HASSAN;SAEED;
*/

using namespace std;
int mod=1e9+7;
int pwr(int b,int e=mod-2ll){
    int mul=b;
    int ret=1;
    while(e){
        if(e&1ll){
            ret*=mul;
            ret%=mod;
        }
        mul*=mul;
        mul%=mod;
        e>>=1;
    }
    return ret;
}


int prf[2000000+5];

int p=31;

int hsh(int l,int r){
    if(l>r)
        return 0;
    return ((((prf[r+1]-prf[l])%mod*pwr(pwr(p,l)))%mod+mod)%mod);
}


int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ppw=p;
    prf[0]=0ll;
    for(int i=0;i<n;i++){
        prf[i+1]=(prf[i]+ppw*(s[i]-'A'))%mod;
        prf[i+1]%=mod;
        ppw*=p;
        ppw%=mod;
    }
    int lst=-1;
    int cnt=0;
    unordered_map<int,int>mp;
    for(int i=0;i<n;i++){
        int hsh1=hsh(0,min(n/2,i)-1)+(hsh(i+1,n/2+(i<=n/2-1)-1)*pwr(p,min(n/2,i)))%mod;
        hsh1%=mod;
        int hsh2=hsh(n-(n/2)-(i>=n-(n/2)),i-1)+(hsh(max(i+1,n-(n/2)-(i>=n-(n/2))),n-1-(i==n-1))*pwr(p,max(0ll,i-(n-(n/2)-(i>=n-(n/2))))))%mod;
        hsh2%=mod;

        if(hsh1==hsh2){
            cnt++;
            lst=i;
            mp[hsh1]++;
        }
        ///cout<<hsh1<<' '<<hsh2<<'\n';

    }
    if(!cnt||n%2==0ll)
        cout<<"NOT POSSIBLE\n";
    else if(mp.size()>1)
        cout<<"NOT UNIQUE\n";
    else{
        for(int i=0;i<n/2+(lst<n/2);i++){
            if(i==lst)continue;
            cout<<s[i];
        }
    }
    return 0;
}

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