Submission #398831

#	Time	Username	Problem	Language	Result	Execution time	Memory
398831		Mohammed_Alsaad	Three Friends (BOI14_friends)	C++17	100 / 100	82 ms	22724 KiB

friends

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

template <typename A, typename B> string to_string(pair<A, B> p);
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p);

string to_string(const string &s)
{
    return '"' + s + '"';
}
string to_string(const char *s)
{
    return to_string((string)s);
}
string to_string(bool b)
{
    return (b ? "true" : "false");
}
// string to_string(vector<bool> v)
// {
//     bool first = true;
//     string res = "{";
//     for (ll i = 0; i < static_cast<ll>(v.size()); i++)
//     {
//         if (!first)
//         {
//             res += ", ";
//         }
//         first = false;
//         res += to_string(v[i]);
//     }
//     res += "}";
//     return res;
// }
template <size_t N> string to_string(bitset<N> v)
{
    string res = "";
    for (size_t i = 0; i < N; i++)
    {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}
template <typename A> string to_string(A v)
{
    bool first = true;
    string res = "{";
    for (const auto &x : v)
    {
        if (!first)
        {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B> string to_string(pair<A, B> p)
{
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " +
           to_string(get<3>(p)) + ")";
}
void dbg_out()
{
    cout << endl;
}
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T)
{
    cout << " " << to_string(H);
    dbg_out(T...);
}

#define FAST_IO                                                                                                        \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(NULL);                                                                                                     \
    cout.tie(NULL);

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]:", dbg_out(__VA_ARGS__)
#define edl() cout << endl;

#define rep(i, a, b) for (ll i = a; i < b; i++)

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define pf push_front

#define F first
#define S second

#define max_self(x, y) x = max(x, y)
#define min_self(x, y) x = min(x, y)

typedef long long ll;
ll const INF = 2147483647, R_INF = 9223372036854775807, MOD = 1e9 + 7;

const ll mxN = 2e6 + 7;

ll po[mxN];

ll hsh(string str)
{
    ll ans = 0;
    for (ll i = str.size() - 1; i >= 0; i--)
        ans = (ans + (str[i] - 'A') * po[str.size() - i - 1]) % MOD;

    return ans;
}

int main()
{
    FAST_IO;

    ll n;
    cin >> n;
    string input;
    cin >> input;

    if (n % 2 == 0)
        return cout << "NOT POSSIBLE", 0;

    po[0] = 1;
    rep(i, 1, n) po[i] = (po[i - 1] * 27) % MOD;

    string res;
    ll val = -1;
    if (input.substr(1, n / 2) == input.substr(n / 2 + 1, n - 1))
        res = input.substr(1, n / 2), val = hsh(res);
    if (input.substr(0, n / 2 - 1) == input.substr(n / 2 + 1, n - 1))
    {
        if (!res.empty() && res != input.substr(0, n / 2 - 1))
            return cout << "NOT UNIQUE", 0;
        else
            res = input.substr(0, n / 2 - 1), val = hsh(res);
    }

    // dbg(input.substr(1, n / 2), input.substr(n / 2 + 1, n));
    ll cur_val = hsh(input.substr(1, n / 2)), cur_ans = hsh(input.substr(n / 2 + 1, n));

    // dbg(cur_val, cur_ans);
    ll idx = n / 2 - 1;
    rep(i, 1, n / 2 + 1)
    {
        cur_val = (cur_val - po[idx] * (input[i] - 'A')) % MOD;
        cur_val = (cur_val + po[idx] * (input[i - 1] - 'A')) % MOD;
        idx--;

        if (cur_val < 0)
            cur_val += MOD;

        if (cur_val == cur_ans)
        {
            if (val == -1)
            {
                val = cur_val;
                rep(j, 0, n / 2 + 1) if (j != i) res += input[j];
            }
            else if (cur_val != val)
                return cout << "NOT UNIQUE", 0;
        }
    }

    // dbg(n, input, n / 2, n / 2 - 1);
    // dbg(input.substr(0, n / 2), input.substr(n / 2 + 1, n));
    cur_val = hsh(input.substr(n / 2 + 1, n)), cur_ans = hsh(input.substr(0, n / 2));
    idx = n / 2 - 1;

    rep(i, n / 2 + 1, n)
    {
        cur_val = (cur_val - po[idx] * (input[i] - 'A')) % MOD;
        cur_val = (cur_val + po[idx] * (input[i - 1] - 'A')) % MOD;
        idx--;

        if (cur_val < 0)
            cur_val += MOD;

        if (cur_val == cur_ans)
        {
            if (val == -1)
            {
                val = cur_val;
                rep(j, n / 2, n) if (j != i) res += input[j];
            }
            else if (cur_val != val)
                return cout << "NOT UNIQUE", 0;
        }
    }

    if (res.empty())
        cout << "NOT POSSIBLE";
    else
        cout << res;
}

/*

n = 9
ABCDEFGHI
ABCE

[ans, (str[i] - 'A')]: 2 2
[ans, (str[i] - 'A')]: 77 23
[ans, (str[i] - 'A')]: 2080 1
"BXC" 2080

[ans, (str[i] - 'A')]: 2 2
[ans, (str[i] - 'A')]: 77 23
[ans, (str[i] - 'A')]: 2079 0
"AXC" 2079

[ans, (str[i] - 'A')]: 2 2
[ans, (str[i] - 'A')]: 55 1
[ans, (str[i] - 'A')]: 1485 0
"ABC" 1485

*/

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