Submission #1184411

#TimeUsernameProblemLanguageResultExecution timeMemory
1184411qrnThree Friends (BOI14_friends)C++20
0 / 100
289 ms50268 KiB
#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 = 41;

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;
    inv[0] = 1;
    for(intt i = 1; i < N; i++) {
        pw[i] = (pw[i-1] * base) % mod;
        inv[i] = binpow(pw[i], mod-2);
    }

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

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

    function<intt(intt, intt, intt, intt)> combined_hasval = [&] (intt l1, intt r1, intt l2, intt r2) -> intt {
        intt solh = hasval(l1, r1);
        intt sagh = hasval(l2, r2) * pw[r1-l1+1];
        sagh%=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;
    while (tst--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...