Решение задачи "Две перемешанные последовательности" с Codeforces

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


Были заданы две последовательности — одна из них была строго возрастающей, а другая — строго убывающей.

Строго возрастающая последовательность — это последовательность целых чисел [x1y2>⋯>yl]. Заметьте, что пустая последовательность и последовательность, состоящая из одного элемента, могут являться как возрастающими, так и убывающими.

Они были объединены в одну последовательность a. После этого последовательность a была перемешана. Например, некоторыми возможными результирующими последовательностями a для возрастающей последовательности [1,3,4] и убывающей последовательности [10,4,2] являются последовательности [1,2,3,4,4,10] и [4,2,1,10,4,3].

Эта перемешанная последовательность a задана во входных данных.

Ваша задача — найти любые две подходящие изначальные последовательности. Одна из них должна быть строго возрастающей, а другая — строго убывающей. Заметьте, что пустая последовательность и последовательность, состоящая из одного элемента, могут являться как возрастающими, так и убывающими.

Если входные данные противоречивы и невозможно разбить заданную последовательность a на убывающую и возрастающую последовательности, выведите «NO».

Код

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

bool comp(int a, int b){return a > b;}

int main(){
    int n;
    cin >> n;
    vector<int>a(200001,0);
    int x;
    for(int i=0;i<n;i++){cin>>x;
    a[x]++;
    if(a[x]>2){cout<<"NO";return 0;}
    }
    cout<<"YES"<<endl;
    int k=0;
    for(int i = 0; i < 200001; i++)
        if(a[i] > 0)
            k++;
    cout << k << endl;
    for(int i = 0;i < 200001; i++)if(a[i] > 0){ a[i]--; cout << i << " ";}
    cout << endl;
    cout<<n - k <<endl;
    for(int i = 200000; i >= 0; i--)if(a[i] > 0)cout << i << " ";
}

         

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


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

Комментарии

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