Submission #529011

#	Time	Username	Problem	Language	Result	Execution time	Memory
529011		perchuts	Three Friends (BOI14_friends)	C++17	0 / 100	86 ms	36344 KiB

friends

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

const ll MOD = 1e9+9;
const ll P = 9887;

vector<ll>pw,prHash;


int main(){_
    int n;string s;cin>>n>>s;
    pw.pb(1);
    while(sz(pw)!=n+1)pw.pb((pw.back()*P)%MOD);
    prHash.resize(n+1);
    prHash[0] = 0;
    if(n%2==0){
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }
    for(int i=0;i<n;++i)prHash[i+1] = (s[i] + (P*prHash[i])%MOD)%MOD;
    
    auto calcHash = [&](int l,int r){
        if(l>r)return 0ll;
        return (MOD + prHash[r+1] - (prHash[l]*pw[r-l+1])%MOD)%MOD;
    };
    int ans = -1,cnt=0;
    for(int i=0;i<n;++i){//try to remove every character from string
        if(i<n/2){
            ll left = calcHash(0,i-1);
            ll right = calcHash(i+1,n/2);
            ll rest = calcHash(n/2+1,n-1);
            ll tot = ((left*pw[n/2-i])%MOD + right)%MOD; 
            if(tot==rest)++cnt, ans = i;
        }else if(i==n/2){
            if(calcHash(0,n/2-1)==calcHash(n/2+1,n-1))++cnt,ans=i;
        }else{
            ll rest = calcHash(0,n/2-1);
            ll left = calcHash(n/2,i-1);
            ll right = calcHash(i+1,n-1);
            ll tot = ((left*pw[n-i-1])%MOD+right)%MOD;
            if(tot==rest)++cnt,ans = i;
        }
    }
    if(cnt==0)cout<<"NOT POSSIBLE";
    else if(cnt>1)cout<<"NOT UNIQUE";
    else cout<<(ans>=n/2?s.substr(0,n/2):s.substr(n/2+1,n/2));
    cout<<endl;
}

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