Submission #1184431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184431		qrn	Three Friends (BOI14_friends)	C++20	0 / 100	89 ms	50448 KiB

friends

#include <bits/stdc++.h>
using namespace std;

#define SPEED ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mxN = 2e5 + 5;
const intt inf = 1e18;
const intt mod = 1e9 + 7;
const intt base = 9973;

intt binpow(intt a, intt b) {
    int res = 1;
    while(b) {
        if(b & 1)  res = (res * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return res;
}

void solve() {
    intt N;
    string s;
    cin >> N >> s;

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

    vector<intt> pw(N + 1, 0ll), inv(N + 1, 0ll), hsh(N + 1, 0ll);
    pw[0] = 1;
    for(intt i = 1; i < N; i++) {
        pw[i] = (pw[i-1] * base) % mod;
    }

    hsh[0] = ((s[0] - 'A' + 1) * pw[0]) % mod;
    for(intt i = 1; i < N; i++) {
        hsh[i] = (hsh[i-1] * base + (s[i] - 'A' + 1)) % mod;
    }

    function<intt(intt, intt)> hasval = [&] (intt l, intt r) -> intt {
        if(l == 0) return hsh[r];
        intt val = (hsh[r] - (hsh[l-1] * pw[r-l+1])) % mod;
        while(val < 0) val += mod;
        return val % mod;
    };

    function<intt(intt, intt, intt, intt)> combined_hasval = [&] (intt l1, intt r1, intt l2, intt r2) -> intt {
        intt solh = hasval(l1, r1) * pw[r2-l2+1];
        intt sagh = hasval(l2, r2);
        solh%=mod;
        
        // if(l2 == r2 && l2 == 3) {
        //     cout << solh << " " << sagh << endl;
        // }
        intt combh = solh % mod;
        combh = (combh + sagh) % mod;
        return combh;
    };

    intt cnt = 0;
    intt koko = -1, koko1 = -1, koko2 = -1;
    if(hasval(1, N/2) == hasval(N/2+1, N-1)) {
        cnt++;
        koko1 = 0;
    }
    if(hasval(0, N/2-1) == hasval(N/2, N-2)) {
        cnt++;
        koko2 = 0;
    }

    for(intt i = 1; i < N - 1; i++) {
        if(i == N / 2 && hasval(0, i-1) == hasval(i+1, N-1)) {
            cnt++;
            koko = i;
        } else if(i < N / 2 && combined_hasval(0, i-1, i+1, N - N/2-1) == hasval(N-N/2, N-1)) {
            cnt++;
            koko1 = i;
        } else if(i > N / 2 && hasval(0, N/2-1) == combined_hasval(N/2, i-1, i+1, N-1)) {
            cnt++;
            koko2 = i;
        }
    }
    if(cnt > 1) {
        cout << "NOT UNIQUE" << endl;
    } else {
        if(cnt == 0) {
            cout << "NOT POSSIBLE" << endl;
        } else {
            if(koko != -1){
                for(intt i = 0; i < koko1; i++) {
                    cout << s[i];
                }
            } else if(koko1 != -1) {
                for(intt i = N - N / 2; i < N; i++)  {
                    cout << s[i];
                }
            } else {
                for(intt i = 0; i < N / 2; i++) {
                    cout << s[i];
                }
            }
        }
    }
    cout << endl;
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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