Submission #1243186

#TimeUsernameProblemLanguageResultExecution timeMemory
1243186chikien2009Three Friends (BOI14_friends)C++20
100 / 100
13 ms8104 KiB
#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n;
string s;
bool a, b;

inline bool Check(string edited, string base)
{
    bool pre[base.size()], suf[base.size()];
    for (int i = 0; i < base.size(); ++i)
    {
        pre[i] = (i == 0 || pre[i - 1]) && (edited[i] == base[i]);
    }
    for (int i = base.size() - 1; i >= 0; --i)
    {
        suf[i] = (i == base.size() - 1 || suf[i + 1]) && (base[i] == edited[i + 1]);
    }
    for (int i = 0; i < edited.size(); ++i)
    {
        if ((i == 0 || pre[i - 1]) && (i == edited.size() - 1 || suf[i]))
        {
            return true;
        }
    }
    return false;
}

int main()
{
    setup();

    cin >> n >> s;
    if (!(n & 1))
    {
        cout << "NOT POSSIBLE";
        return 0;
    }
    a = Check(s.substr(0, n / 2 + 1), s.substr(n / 2 + 1, n / 2));
    b = Check(s.substr(n / 2, n / 2 + 1), s.substr(0, n / 2));
    if (a && b)
    {
        cout << (s.substr(0, n / 2) == s.substr(n / 2 + 1, n / 2) ? s.substr(0, n / 2) : "NOT UNIQUE");
    }
    else if (a)
    {
        cout << s.substr(n / 2 + 1, n / 2);
    }
    else if (b)
    {
        cout << s.substr(0, n / 2);
    }
    else
    {
        cout << "NOT POSSIBLE";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...