Submission #476744

#TimeUsernameProblemLanguageResultExecution timeMemory
476744SamAndThree Friends (BOI14_friends)C++17
100 / 100
88 ms7160 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 2000006;
 
int n;
char aa[N], a[N];
 
int pp, ss;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n >> aa;
    for (int i = 1; i <= n; ++i)
        a[i] = aa[i - 1];
    if (n % 2 == 0)
    {
        cout << "NOT POSSIBLE" << endl;
        return 0;
    }
    for (int i = 1, j = n / 2 + 2; i <= n / 2; ++i, ++j)
    {
        if (a[i] != a[j])
            break;
        ++pp;
    }
    for (int i = n / 2 + 1, j = n; j > n / 2 + 1; --i, --j)
    {
        if (a[i] != a[j])
            break;
        ++ss;
    }
    bool z2 = false;
    for (int i = 1; i <= n / 2; ++i)
    {
        if (pp >= i - 1 && ss >= (n / 2 - i + 1))
        {
            z2 = true;
            break;
        }
    }
    pp = ss = 0;
    for (int i = 1, j = n / 2 + 1; i <= n / 2; ++i, ++j)
    {
        if (a[i] != a[j])
            break;
        ++pp;
    }
    for (int i = n / 2, j = n; i >= 1; --i, --j)
    {
        if (a[i] != a[j])
            break;
        ++ss;
    }
    bool z1 = false;
    for (int i = n / 2 + 2; i <= n; ++i)
    {
        if (ss >= (n - i) && pp >= (i - n / 2 - 1))
        {
            z1 = true;
            break;
        }
    }
    bool z = true;
    for (int i = 1, j = n / 2 + 2; i <= n / 2; ++i, ++j)
    {
        if (a[i] != a[j])
        {
            z = false;
            break;
        }
    }
    if (!z && !z1 && !z2)
    {
        cout << "NOT POSSIBLE" << endl;
        return 0;
    }
    if (z1 && z2 && !z)
    {
        cout << "NOT UNIQUE" << endl;
        return 0;
    }
    if (z1 || z)
    {
        for (int i = 1; i <= n / 2; ++i)
        {
            cout << a[i];
        }
        cout << endl;
        return 0;
    }
    if (z2)
    {
        for (int i = n / 2 + 2; i <= n; ++i)
        {
            cout << a[i];
        }
        cout << endl;
        return 0;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...