Submission #938378

#	Time	Username	Problem	Language	Result	Execution time	Memory
938378		Ghulam_Junaid	Three Friends (BOI14_friends)	C++17	0 / 100	92 ms	25020 KiB

friends

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

typedef long long ll;

const ll mod = 998244353;
const ll base = 1e6 + 1;

int main(){
    ll n;
    string s;
    cin >> n >> s;

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

    ll k = n / 2;
    ll hsh = 0;

    ll pw[n];
    pw[0] = 1;
    for (ll i = 1; i < n; i ++)
        pw[i] = (pw[i - 1] * base) % mod;

    ll pref = 0;
    ll suff = 0;

    ll poss = 0;

    string P, S;

    for (ll i = 0; i < k; i ++)
        pref = (pref * base + s[i]) % mod, P += s[i];
    for (ll i = k + 1; i < n; i ++)
        suff = (suff * base + s[i]) % mod, S += s[i];

    for (ll i = 1; i <= k; i ++)
        hsh = (hsh * base + s[i]) % mod;

    for (ll i = 0; i < k; i ++){
        poss += (hsh == suff);
        hsh += pw[k - i - 1] * s[i];
        hsh = ((hsh % mod) + mod) % mod;
        hsh -= pw[k - i - 1] * s[i + 1];
        hsh = ((hsh % mod) + mod) % mod;
    }

    string ans;
    if (poss)
        ans = S;

    ll nposs = 0;
    hsh = suff;
    for (ll i = k, j = k - 1; i + 1 < n; i ++, j--){
        nposs += (hsh == pref);
        hsh -= s[i + 1] * pw[j];
        hsh = ((hsh % mod) + mod) % mod;
        hsh += s[i] * pw[j];
        hsh = ((hsh % mod) + mod) % mod;
    }
    nposs += (hsh == pref);

    if (nposs)
        ans = P;

    poss += nposs;

    if (poss > 1)
        cout << "NOT UNIQUE" << endl;
    else if (poss == 0)
        cout << "NOT POSSIBLE" << endl;
    else
        cout << ans << endl;
}

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