Submission #1340030

#TimeUsernameProblemLanguageResultExecution timeMemory
1340030mahesh_9996Three Friends (BOI14_friends)C++20
35 / 100
1098 ms67988 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll MOD1 = 1000000007;
const ll MOD2 = 1000000009;
const ll BASE = 91138233;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string U;
    cin >> U;

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

    int n = (N - 1) / 2;

    // Precompute powers
    vector<ll> pow1(N + 1), pow2(N + 1);
    pow1[0] = pow2[0] = 1;
    for (int i = 1; i <= N; i++) {
        pow1[i] = (pow1[i - 1] * BASE) % MOD1;
        pow2[i] = (pow2[i - 1] * BASE) % MOD2;
    }

    // Prefix hashes
    vector<ll> h1(N + 1, 0), h2(N + 1, 0);
    for (int i = 0; i < N; i++) {
        h1[i + 1] = (h1[i] * BASE + U[i]) % MOD1;
        h2[i + 1] = (h2[i] * BASE + U[i]) % MOD2;
    }

    auto get_hash = [&](int l, int r) {
        // [l, r)
        ll x1 = (h1[r] - h1[l] * pow1[r - l]) % MOD1;
        ll x2 = (h2[r] - h2[l] * pow2[r - l]) % MOD2;
        if (x1 < 0) x1 += MOD1;
        if (x2 < 0) x2 += MOD2;
        return pair<ll,ll>{x1, x2};
    };

    set<string> candidates;

    for (int i = 0; i < N; i++) {
        // Build hash of V (U without i-th char)

        // First half: length n
        // Second half: length n

        // We simulate indexing in V
        // Map V index → U index

        auto getV = [&](int l, int r) {
            // returns hash of V[l, r)
            // map to U skipping i
            if (r <= i) {
                return get_hash(l, r);
            } else if (l >= i) {
                return get_hash(l + 1, r + 1);
            } else {
                // split
                auto left = get_hash(l, i);
                auto right = get_hash(i + 1, r + 1);

                int lenR = r - i;
                ll x1 = (left.first * pow1[lenR] + right.first) % MOD1;
                ll x2 = (left.second * pow2[lenR] + right.second) % MOD2;
                return pair<ll,ll>{x1, x2};
            }
        };

        auto hA = getV(0, n);
        auto hB = getV(n, 2 * n);

        if (hA == hB) {
            // construct S explicitly (only when needed)
            string S;
            S.reserve(n);
            for (int j = 0; j < N; j++) {
                if (j == i) continue;
                if ((int)S.size() < n)
                    S.push_back(U[j]);
            }
            candidates.insert(S);

            if (candidates.size() > 1) {
                cout << "NOT UNIQUE\n";
                return 0;
            }
        }
    }

    if (candidates.empty()) {
        cout << "NOT POSSIBLE\n";
    } else {
        cout << *candidates.begin() << "\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...