Submission #394489

#	Time	Username	Problem	Language	Result	Execution time	Memory
394489		ak2006	Three Friends (BOI14_friends)	C++14	35 / 100	763 ms	45304 KiB

friends

#include <bits/stdc++.h>
using namespace std;
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;
}
int 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];
    set<int>vals;

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

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

    for (int i = 0;i<n;i++){
        if (i == 0){
            ll v1 = ((hsh[len] - hsh[0])%mod + mod)%mod;
            ll v2 = ((hsh[n - 1] - hsh[len])%mod + mod)%mod;
            if ((v1 * power[len])%mod == v2){
                vals.insert((v1 * inv(p))%mod);
                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;
            if ((v1 * power[len])%mod == v2){
                vals.insert((v1 * inv(p))%mod);
                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;
            if ((v1 * power[len + 1])%mod == v2){
                vals.insert(v1);
                start = 0;
            }
        }
    }
    cnt = vals.size();
    if (cnt > 1)cout<<"NOT UNIQUE";
    else if (cnt == 0)cout<<"NOT POSSIBLE";
    else cout<<s.substr(start,len);
    return 0;
}

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