제출 #340193

#제출 시각아이디문제언어결과실행 시간메모리
340193blue세 명의 친구들 (BOI14_friends)C++11
100 / 100
61 ms7256 KiB
#include <iostream>
#include <string>
#include <set>
using namespace std;

/*
S must be equal to either the first half or second half of the string.
*/

int main()
{
    int N;
    cin >> N;

    string U;
    cin >> U;

    if(N % 2 == 0)
    {
        cout << "NOT POSSIBLE\n";
        return 0;
    }
    int a = 0, b = N/2, c = N/2 + 1;

    bool flag = 0;
    //Check if the first floor(half) of the string is equal to S
    int i = 0, j = b - 1;

    int psbl1 = 1, psbl2 = 1;
    int x = 0;

    for(i = 0; i < N/2; i++)
    {
        j++;
        if(U[i] == U[j])
        {
            x++;
            continue;
        }
        if(flag)
        {
            psbl1 = 0;
            break;
        }
        j++;
        flag = 1;

        if(U[j] == U[i])
        {
            x++;
        }
    }
    if(x != N/2) psbl1 = 0;

    //Check if the last floor(half) of the string is equal to S
    flag = 0;
    i = c;
    j = -1;
    x = 0;
    for(i = c; i < N; i++)
    {
        j++;
        if(U[i] == U[j])
        {
            //cout << i << ' ' << j << '\n';
            x++;
            continue;
        }
        if(flag)
        {
            psbl2 = 0;
            break;
        }
        j++;
        flag = 1;
        if(U[j] == U[i])
        {
            x++;
        }
    }
    //cout << x << '\n';
    if(x != N/2) psbl2 = 0;
//    cout << psbl1 << psbl2 << '\n';


    if(!psbl1 && !psbl2)
    {
        cout << "NOT POSSIBLE\n";
    }
    else if(psbl1 && psbl2)
    {
        if(U.substr(0, N/2) == U.substr(c, N/2))
        {
            cout << U.substr(0, N/2) << '\n';
        }
        else cout << "NOT UNIQUE\n";
    }
    else if(psbl1)
    {
        cout << U.substr(a, N/2) << '\n';
    }
    else
    {
        cout << U.substr(c, N/2) << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...