제출 #361959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361959		Ahmad_Hasan	세 명의 친구들 (BOI14_friends)	C++17	0 / 100	1089 ms	18064 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])*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');
        ppw*=p;
        ppw%=mod;
    }
    int lst=-1;
    int cnt=0;
    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;
        }
        ///cout<<hsh1<<' '<<hsh2<<'\n';

    }
    if(!cnt||n%2==0ll)
        cout<<"NOT POSSIBLE\n";
    else if(cnt>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: 0 / 35
• Subtask 2: 0 / 65