Codeforces Round #550 (Div. 3) C. Two Shuffled Sequences

C. Two Shuffled Sequences

https://codeforces.com/contest/1144/problem/C

주어진 수들을 단조 증가, 단조 감소하는 집합으로 표현할 수 있어야 한다.

이것이 만들어질 수 있는 조건은 "같은 수가 3개 이상 존재하지 않을 것" 밖에 없다.

정렬을 한 후에, 하나씩 단조 증가, 단조 감소하는 vector에 넣어주면 된다.

이때, 전 index와 같은 수가 나온다면 직전 index와 다른 집합에 넣어준다.

다 구했다면, 차례대로 출력하는데 단조 감소는 뒤에서부터 출력해주자.

#include <bits/stdc++.h>
using namespace std;
 
int n;
int arr[200001];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    sort(arr, arr + n);
    
    vector<int> up, down;
    up.push_back(arr[0]);
 
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1]) down.push_back(arr[i]);
        else up.push_back(arr[i]);
 
        if (i > 1) {
            if (arr[i] == arr[i - 1] && arr[i - 1] == arr[i - 2]) {
                puts("NO");
                exit(0);
            }
        }
    }
 
    cout << "Yes\n";
    cout << up.size() << '\n';
    for (int i = 0; i < up.size(); i++) {
        cout << up[i] << ' ';
    }
 
    cout << '\n' << down.size() << '\n';
 
    for (int i = down.size() - 1; i >= 0; i--) {
        cout << down[i] << ' ';
    }
 
    return 0;
}