Submission #851142

#	Time	Username	Problem	Language	Result	Execution time	Memory
851142		emkow	Three Friends (BOI14_friends)	C++17	100 / 100	98 ms	45800 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;
            if(pw[i] >= mod) pw[i] %= mod;
        }
        h.resize(n + 1);
        for(int i = 1; i <= n; i ++){
            ll x = (pw[i] * (ll)(s[i - 1] - 'A' + 1));
            if(x >= mod) x %= mod;
            h[i] = h[i - 1] + x;
            if(h[i] >= mod) h[i] %= mod;
        }
    }
    ll get(int a, int b){
        ll r = (h[b] - h[a - 1] + mod) % mod;
        r = (r * pw[n - a]);
        if(r >= mod) r %= mod;
        return r;
    }
    ll gett(int a, int b, int c, int d){
        ll h1 = get(a, b), h2 = get(c, d);
        h2 = (h2 * pw[b - a + 1]);
        if(h2 >= mod) h2 %= mod;
        ll r = (h1 + h2);
        if(r >= mod) r %= 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);
    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(H.get(1, 1 + l - 1) == H.get(n - l, n - 1)) ev.pb(n);
    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(k + 1, n);
            for(int i = 1; i < ssize(ev); i ++){
                if(ev[i] < k) continue;
                if(hsh != H.get(1, l)) 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: 65 / 65