Submission #106863

#	Time	Username	Problem	Language	Result	Execution time	Memory
106863		someone_aa	Three Friends (BOI14_friends)	C++17	0 / 100	78 ms	10992 KiB

friends

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll p = 31LL;
const ll mod = 1000000009LL;
const int maxn = 200100;
ll pp[maxn], pref[maxn], n;
string code;
 
ll power(ll a, ll b) {
    // return a^b % mod
    if(b == 0LL) return 1LL;
    else if(b== 1LL) return a;
    else {
        if(b % 2 == 0) {
            ll half = power(a, b/2);
            return (half*half)%mod;
        }
        else if(b % 2 == 1) {
            ll half = power(a, b-1);
            return ((half)*a)%mod;
        }
    }
}
 
void get_consts() {
    pp[0] = 1LL;
    for(int i=1;i<maxn;i++) {
        pp[i] = pp[i-1] * p;
        pp[i] %= mod;
    }
}
 
void get_prefhash() {
    pref[0] = 0LL;
    for(int i=1;i<=n;i++) {
        pref[i] += pref[i-1];
        pref[i] += pp[i] * (code[i] - 'A' + 1LL);
        pref[i] %= mod;
    }
}
 
ll subhash(ll i, ll j) {
    ll tmp = 1LL * pref[j] + mod - pref[i-1];
    tmp %= mod;
    tmp *= 1LL * power(pp[i-1], mod-2);
    tmp %= mod;
    return 1LL * tmp;
}
 
ll mergehash(ll hasha, ll hashb, ll k) {
    //cout<<hasha<<" "<<hashb<<" "<<k<<"\n";
    ll temp = (hashb * pp[k])%mod;
    temp = temp + hasha;
    temp %= mod;
    //cout<<temp<<"\n";
    return temp;
}
 
int main() {
    get_consts();
    cin>>n;
    cin>>code; code = "#" + code;
    get_prefhash();
    if(n % 2 == 0) {
        cout<<"NOT POSSIBLE\n";
        return 0;
    }
    ll cnt = 0;
    ll answ = 0;
 
 
    for(int i=2;i<n;i++) {
       //cout<<i<<" -> ";
        if(i == n / 2 + 1) {
         //   cout<<"A\n";
            if(subhash(1, i-1) == subhash(i+1, n)) {
                cnt++;
                answ = i;
            }
        }
        else if( i < n/2+1) {
            if(mergehash(subhash(1, i-1), subhash(i+1, n/2+1), i-1) == subhash(n/2+2, n)) {
                cnt++;
                answ = i;
            }
        }
        else if ( i > n/2+1) {
            if(mergehash(subhash(n/2+1, i-1), subhash(i+1, n),(i-1)-(n/2+1)+1) == subhash(1, n/2)) {
                cnt++;
                answ = i;
            }
        }
    }
 
    if(subhash(2, n/2+1) == subhash(n/2+2, n)) {
        cnt++;
        answ = 1;
    }
    if(subhash(1, n/2) == subhash(n/2+1, n-1)) {
        cnt++;
        answ = n;
    }
 
    if(cnt == 0) {
        cout<<"NOT POSSIBLE\n";
    }
    else if(cnt == 1) {
        if(answ >= n/2+1) {
            for(int i=1;i<=n/2;i++) {
                cout<<code[i];
            }
        }
        else {
            for(int i=n/2+2;i<=n;i++) {
                cout<<code[i];
            }
        }
    }
    else {
        cout<<"NOT UNIQUE\n";
    }
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'long long int power(long long int, long long int)':
friends.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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