Submission #851120

#	Time	Username	Problem	Language	Result	Execution time	Memory
851120		emkow	Three Friends (BOI14_friends)	C++17	35 / 100	748 ms	34796 KiB

friends

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define pb emplace_back
#define ins insert
#define ssize(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pld pair <ld, ld>
#define st first
#define nd second

using namespace std;
using ll = int_fast64_t;
// using lll = __int128_t;
using ld = long double;
const int oo = 1e9 + 7;
const int mod = 1e9 + 9;

struct Hash{
    int n, p = 2137;
    vector <ll> h, pw;
    Hash(string &s){
        n = s.length();
        pw.resize(n + 1);
        pw[0] = 1;
        for(int i = 1; i <= n; i ++) pw[i] = (pw[i - 1] * p) % mod;
        h.resize(n + 1);
        for(int i = 1; i <= n; i ++) h[i] = (h[i - 1] + (pw[i] * (ll)(s[i - 1] - 'A' + 1)) % mod) % mod;
    }
    ll fp(ll a, ll b){
        ll r = 1;
        while(b > 0){
            if(b & 1) r = (r * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return r;
    }
    ll get(int a, int b){
        ll r = (h[b] - h[a - 1] + mod) % mod;
        r = (r * fp(pw[a], mod - 2)) % mod;
        return r;
    }
    ll gett(int a, int b, int c, int d){
        ll h1 = get(a, b), h2 = get(c, d);
        ll r = (h1 + (h2 * pw[b - a + 1]) % mod) % mod;
        return r;
    }
};

void solve(){
    int n; cin >> n;
    string s; cin >> s;
    if(!(n & 1)){
        cout << "NOT POSSIBLE\n";
        return;
    }
    Hash H(s);
    vector <int> ev;
    int k = (n + 1) / 2, l = n / 2;
    if(H.get(2, 2 + l - 1) == H.get(n - l + 1, n)) ev.pb(1);
    if(H.get(1, 1 + l - 1) == H.get(n - l, n - 1)) ev.pb(n);
    for(int i = 2; i < n; i ++){
        if(i == k){
            if(H.get(1, k - 1) == H.get(k + 1, n)) ev.pb(i);
        }
        if(i < k){
            if(H.get(n - l + 1, n) == H.gett(1, i - 1, i + 1, k)) ev.pb(i);
        }
        if(i > k){
            if(H.get(1, l) == H.gett(k, i - 1, i + 1, n)) ev.pb(i);
        }
    }
    if(!ssize(ev)){
        cout << "NOT POSSIBLE\n";
        return;
    }
    int idx = ev[0];
    if(ssize(ev) > 1){
        ll hsh = 0;
        bool ok = 1;
        if(idx >= k) hsh = H.get(1, l);
        else hsh = H.get(k + 1, n);
        for(int i = 1; i < ssize(ev); i ++){
            if(ev[i] >= k && hsh != H.get(1, l)) ok = 0;
            if(ev[i] < k && hsh != H.get(k + 1, n)) ok = 0;
        }
        if(!ok){
            cout << "NOT UNIQUE\n";
            return;
        }
    }
    if(idx >= k){
        for(int i = 1; i <= l; i ++) cout << s[i - 1];
    }
    else{
        for(int i = n - l + 1; i <= n; i ++) cout << s[i - 1];
    }
    cout << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; t = 1;
    // cin >> t;
    while(t --) solve();
    return 0;
}

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