[정올] 1356 / [백준] 2505 / 두번 뒤집기

// Preset 생략

int n;
CVector<int> inc;
CVector<int> old;

pii sol_fs()
{
    for (int i = 1; i <= n; i++)
    {
        int index = i - 1;
        int num = i;

        if (inc[index] == num)
        {
            continue;
        }

        // 증가 하지 않음
        if (inc[index] == n)
        {
            // 끝에 나와야함
            reverse(inc.begin() + index, inc.end());
            return {index + 1, n};
        }

        for (int j = i + 1; j <= n; j++)
        {
            int jindex = j - 1;
            int jnum = j;

            if (inc[jindex] != num)
                continue;

            // num을 찾음
            reverse(inc.begin() + index, inc.begin() + jindex + 1);
            return {index + 1, jindex + 1};
        }
    }

    return {-1, -1};
}

pii sol_fe()
{
    for (int i = n; i >= 1; i--)
    {
        int index = i - 1;
        int num = i;

        if (inc[index] == num)
        {
            continue;
        }

        // 증가 하지 않음
        if (inc[index] == 1)
        {
            // 끝에 나와야함
            reverse(inc.begin(), inc.begin() + index);
            return {1, index + 1};
        }

        for (int j = i - 1; j >= 1; j--)
        {
            int jindex = j - 1;
            int jnum = j;

            if (inc[jindex] != num)
                continue;

            // num을 찾음
            reverse(inc.begin() + jindex, inc.begin() + index + 1);
            return {jindex + 1, index + 1};
        }
    }

    return {-1, -1};
}

pii sol(int searchFrom)
{
    if (searchFrom == 0)
        return sol_fs();
    else
        return sol_fe();
}

CVector<int> p;

void try_t1(int a, int b)
{
    pii ret = sol(a);
    if (ret.first == -1 && ret.second == -1)
    {
        cout << "1 1\n1 1";
        exit(0);
    }
    p.push(ret.first);
    p.push(ret.second);

    ret = sol(b);
    if (ret.first == -1 && ret.second == -1)
    {
        cout << p[0] << " " << p[1] << "\n"
             << "1 1";
        exit(0);
    }
    p.push(ret.first);
    p.push(ret.second);

    for (int i = 1; i <= n; i++)
    {
        if (inc[i - 1] != i)
        {
            p.fast_pop();
            p.fast_pop();
            p.fast_pop();
            p.fast_pop();
            return;
        }
    }

    cout << p[0] << " " << p[1] << "\n"
         << p[2] << " " << p[3];
    exit(0);
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        inc.push_back(x);
        old.push(x);
    }

    try_t1(0, 0);

    for (int i = 0; i < n; i++)
    {
        inc[i] = old[i];
    }

    pii ret = sol(1);

    if (ret.first == -1 && ret.second == -1)
    {
        cout << "1 1\n1 1";
        return 0;
    }
    cout << ret.first << " " << ret.second << endl;

    ret = sol(1);

    if (ret.first == -1 && ret.second == -1)
    {
        cout << "1 1";
        return 0;
    }
    cout << ret.first << " " << ret.second << endl;
}