Submission #394477

#	Time	Username	Problem	Language	Result	Execution time	Memory
394477		ak2006	Three Friends (BOI14_friends)	C++14	0 / 100	479 ms	53204 KiB

friends

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18,p = 31;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 2e6 + 5;
vi a(n);
vl hsh(n,1),power(n,1);
ll poww(ll a,ll b)
{
    if (b == 0)return 1;
    if (b == 1)return a;
    ll ret = poww(a,b/2);
    if (b%2 == 0)return (ret * ret)%mod;
    return ((ret * ret)%mod * a)%mod;
}
ll inv(ll a)
{
    return (poww(a,mod - 2)%mod + mod)%mod;
}
ll get_hash(int a,int b)
{
    return (((hsh[b] - ((a >= 1 ? hsh[a - 1] : 0))%mod))%mod + mod)%mod;
}
int32_t main()
{
    for (int i = 1;i<=n;i++)power[i] = (power[i - 1] * p)%mod;
    cin>>n;

    if (n % 2 == 0){cout<<"NOT POSSIBLE";return 0;}

    string s;
    cin>>s;

    for (int i = 0;i<n;i++)
        a[i] = s[i] - 'A' + 1;

    hsh[0] = a[0];

    for (int i = 0;i<n - 1;i++)
        hsh[i + 1] = (poww(p,i + 1) * a[i + 1] + hsh[i])%mod;

    //for (int i = 0;i<n;i++)cout<<hsh[i]<<endl;

    int cnt = 0,start = -1,len = (n - 1)/2;

    for (int i = 0;i<n;i++){
        //if i is the point where the third friend inserted the letter then we need

        if (i == 0){
            ll v1 = ((hsh[len] - hsh[0])%mod + mod)%mod;
            ll v2 = ((hsh[n - 1] - hsh[len])%mod + mod)%mod;

            v1 = (v1 * power[len])%mod;

            if (v1 == v2){
                if (!((s.substr(1,len) == s.substr(len + 1,len))))return -1;
                cnt++,start = 1;
            }
        }
        else if (i < len){
            ll v1 = ((((hsh[i - 1] * p)%mod + (hsh[len] - hsh[i]))%mod)%mod + mod)%mod;
            ll v2 = ((hsh[n - 1] - hsh[len])%mod + mod)%mod;
            v1 = (v1 * power[len])%mod;

            if (v1 == v2){
                if (!((s.substr(0,i) + s.substr(i + 1,len - i) == s.substr(len + 1,len))))return -1;
                cnt++,start = len + 1;
            }
        }
        else{
            ll v1 = hsh[len - 1];
            ll v2 = ((((hsh[i - 1] - hsh[len - 1]) * p)%mod + (hsh[n - 1] - hsh[i])%mod)%mod + mod)%mod;
            v1 = (v1 * power[len + 1])%mod;

            assert(v1 >= 0 && v2 >= 0);

            if (v1 == v2){

                if (!(s.substr(0,len) == s.substr(len,i - len) + s.substr(i + 1)))return -1;
                cnt++,start = 0;
            }
        }
    }

    if (cnt > 1)cout<<"NOT UNIQUE";
    else if (cnt == 0)cout<<"NOT POSSIBLE";
    else cout<<s.substr(start,len);
    return 0;
}

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