Решение задачи Последовательность - 2 с Acmp

Без пояснения   Просмотров: 282


Вася написал на доске n целых чисел ai и ушел. Пришел Петя и, увидев Васину последовательность, решил ее немного изменить. Для этого он решил, что может стирать с доски лишь те числа, у которых имеются слева и справа элементы, превосходящие их. Формально, Петя может стереть число ak, если существуют значения ai и aj такие, что ai > ak и aj > ak и i < k < j. Когда на доске не осталось чисел, которые мог стереть Петя, он ушел.

Пришел Вася и очень удивился увиденному. Напишите программу, которая выводит последовательность, которую увидел Вася.

Код

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    bool f = false, temp = false;
    int n, jj, t;
    cin >> n;
    vector<int> b;
    vector<int> a;
    vector<int> aa;
    vector<int> cc;
    for(int i = 0; i < n; ++i){
        cin >> t;
        b.push_back(t);
        a.push_back(t);
    }
    sort(b.begin(), b.end());
    for(int i = 0; i < b.size(); ++i)
        if(b[i] != a[i]){
            f = true;
            break;
        }
    if(!f){
        cout << a.size() << endl;
        for(int i = 0; i < a.size(); ++i)
            cout << a[i] << " ";
        return 0;
    }
    f = false;
    reverse(b.begin(),b.end());
    for(int i = 0; i < a.size(); ++i)
        if(b[i] != a[i]){
            f = true;
            break;
    }
    if(!f){
        cout << a.size() << endl;
        for(int i = 0; i < a.size(); ++i)
            cout << a[i] << " ";
        return 0;
    }
 
 
 
 
 
    f = false;
    b.clear();
    for(int i = 0; i < a.size() - 1; ++i){
        for(int j = i + 1; j < a.size(); ++j){
            if(a[i] <= a[j]){
                b.push_back(a[i]);
                if(b.size() > 1)
                    b.pop_back();
                b.push_back(a[j]);
                i = j;
            }
            if(j == a.size() - 1 && a[j] < a[i])
                f = true;
        }
        if(f){
            jj = i;
            temp = true;
            break;
        }
    }
    if(!b.size() && jj == 0)
        b.push_back(a[0]);
    for(int i = 0; i < b.size(); ++i)
        cc.push_back(b[i]);
    b.clear();
    if(temp){
        temp = false;
        for(int i = jj; i < a.size(); ++i)
            aa.push_back(a[i]);
        reverse(aa.begin(),aa.end());
        f = false;
        for(int i = 0; i < aa.size() - 1; ++i){
            for(int j = i + 1; j < aa.size(); ++j){
                if(aa[i] <= aa[j]){
                    b.push_back(aa[i]);
                    if(b.size() > 1)
                        b.pop_back();
                    b.push_back(aa[j]);
                    i = j ;
                }
                if(j == aa.size() - 1 && aa[j] < aa[i])
                    f = true;
            }
            if(f)
                break;
    }
    }
 
 
    if(b.size()){
        b.pop_back();
        for(int i = b.size() - 1; i >= 0; --i)
            cc.push_back(b[i]);
    }
    cout <<cc.size() <<  endl;
    for(int i = 0; i < cc.size(); ++i)
       cout << cc[i] << " ";
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться