Codeforces Round #550 (Div.3)

CodeForces Contest: http://codeforces.com/contest/1144
Probelm Set PDF: https://file.beiyanpiki.cn/ACM/Codeforces%23550.pdf
官方英文题解: http://codeforces.com/blog/entry/66307

A. Wrong Subtraction

A string is called diverse if it contains consecutive (adjacent) letters of the Latin alphabet and each letter occurs exactly once. For example, the following strings are diverse: "fced", "xyz", "r" and "dabcef". The following string are not diverse: "az", "aa", "bad" and "babc". Note that the letters 'a' and 'z' are not adjacent.

Formally, consider positions of all letters in the string in the alphabet. These positions should form contiguous segment, i.e. they should come one by one without any gaps. And all letters in the string should be distinct (duplicates are not allowed).

You are given a sequence of strings. For each string, if it is diverse, print "Yes". Otherwise, print "No".

###input

The first line contains integer $n$ ( $1 \le n \le 100$ ), denoting the number of strings to process. The following $n$ lines contains strings, one string per line. Each string contains only lowercase Latin letters, its length is between $1$ and $100$ , inclusive.

###output
Print $n$ lines, one line per a string in the input. The line should contain "Yes" if the corresponding string is diverse and "No" if the corresponding string is not diverse. You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

###Examples

####case 1:
| input |output |
| ------------ | ------------ |
|8 fced xyz r dabcef az aa bad babc | Yes Yes Yes Yes No No No No|

###Solve
这是一道900分的签到题。
官方标签：implementation strings

第一行给出字符串个数n
接下来n行每行给出一个字符串s.

定义字符串多样性的应同时满足一下两种条件:

该字符串所有出现的字母都应该是连续的(a与z不是相邻字符)
每个字母只出现一次

如果字符串满足多样性条件，输出YES，否则输出NO.
先给string排序，接着从左向右遍历即可

#include <bits/stdc++.h>

using namespace std;

int main() {
//    freopen("../in", "r", stdin);
//    freopen("../out", "w", stdout);

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        map<char, int> letter;
        bool flag = true;
        for (int i = 0; i < s.length(); i++) {
            letter[s[i]]++;
            if (letter.count(s[i]) > 1)
                flag = false;
            if (i > 0 && s[i] - 1 != s[i - 1])
                flag = false;
        }
        puts(flag ? "Yes" : "No");
    }
}

B. Parity Alternated Deletions

Polycarp has an array $a$ consisting of $n$ integers.

He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains $n-1$ elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-... or odd-even-odd-even-...) of the removed elements. Polycarp stops if he can't make a move.

Formally:

If it is the first move, he chooses any element and deletes it;
If it is the second or any next move:
- if the last deleted element was odd, Polycarp chooses any even element and deletes it;
- if the last deleted element was even, Polycarp chooses any odd element and deletes it.
If after some move Polycarp cannot make a move, the game ends.

Polycarp's goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero.

Help Polycarp find this value.

###input

The first line of the input contains one integer $n$ ( $1 \le n \le 2000$ ) — the number of elements of $a$ .

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 10^6$ ), where $a_i$ is the $i$ -th element of $a$ .

###output
Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.

###Examples

####case 1:
| input |output |
| ------------ | ------------ |
|5 1 5 7 8 2| 0 |

####case 2:
| input |output |
| ------------ | ------------ |
|6 5 1 2 4 6 3| 0 |

####case 3:
| input |output |
| ------------ | ------------ |
|2 1000000 1000000| 1000000 |

###Solve
这是一道1000分的排序题。
官方标签：greedy sortings

第一行给出数列的长度n
第二列给出长度为n的数列 $a$
现在给出一个删除规则：

如果是第一次移动，可以删除任意一个元素
如果是第二次或之后的移动
- 如果上一次删除的是偶数，则需要选择任意一个奇数删除
- 如果上一次删除的是奇数，则需要选择任意一个偶数删除
如果无法进行删除了，则游戏结束

问：数列进行删除规则的操作后，所留下来的数的和的可能最小值。(如果整个数列都被删除了，则为0)

首先将数列 $a$ 的奇数与偶数分开，分别为 $odd , even$ ，并将这两个数列从大到小排序。
设数列 $odd$ 的长度为 $len1$ , $even$ 的长度为 $len2$ 。

如果 $\vert len1 - len2 \vert \leq 1$ , 则数列 $a$ 全部被删除.
如果
- 如果 $len1 < len2$ ，那么 $sum = Sum(even[len1+1],even[len2-1])$
- 如果 $len1 > len2$ ，那么 $sum = Sum(odd[len2+1],odd[len1-1])$

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2005;

int main() {
//    freopen("../in", "r", stdin);
//    freopen("../out", "w", stdout);

    int n;
    vector<int> odd;
    vector<int> even;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        if (t % 2) {
            odd.push_back(t);
        } else {
            even.push_back(t);
        }
    }

    sort(odd.begin(), odd.end(), greater<int>());
    sort(even.begin(), even.end(), greater<int>());

    int s1 = odd.size();
    int s2 = even.size();

    int sum = 0;
    if (s1 >= s2 + 2) {
        for (int i = s1 - 1; i > s2; i--) {
            sum += odd[i];
        }
        cout << sum << endl;
    } else if (s2 >= s1 + 2) {
        for (int i = s2 - 1; i > s1; i--) {
            sum += even[i];
        }
        cout << sum << endl;
    } else {
        cout << "0" << endl;
    }


}

C. Two Shuffled Sequences

Two integer sequences existed initially — one of them was strictly increasing, and the other one — strictly decreasing.

Strictly increasing sequence is a sequence of integers $[x_1 < x_2 < \dots < x_k]$ . And strictly decreasing sequence is a sequence of integers $[y_1 > y_2 > \dots > y_l]$ . Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

They were merged into one sequence $a$ . After that sequence $a$ got shuffled. For example, some of the possible resulting sequences $a$ for an increasing sequence $[1, 3, 4]$ and a decreasing sequence $[10, 4, 2]$ are sequences $[1, 2, 3, 4, 4, 10]$ or $[4, 2, 1, 10, 4, 3]$ .

This shuffled sequence $a$ is given in the input.

Your task is to find any two suitable initial sequences. One of them should be strictly increasing and the other one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

If there is a contradiction in the input and it is impossible to split the given sequence $a$ to increasing and decreasing sequences, print "NO".

###input

The first line of the input contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of elements in $a$ .

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 2 \cdot 10^5$ ), where $a_i$ is the $i$ -th element of $a$ .

###output
If there is a contradiction in the input and it is impossible to split the given sequence $a$ to increasing and decreasing sequences, print "NO" in the first line.

Otherwise print "YES" in the first line and any two suitable sequences. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

In the second line print $n_i$ — the number of elements in the strictly increasing sequence. $n_i$ can be zero, in this case the increasing sequence is empty.

In the third line print $n_i$ integers $inc_1, inc_2, \dots, inc_{n_i}$ in the increasing order of its values ( $inc_1 < inc_2 < \dots < inc_{n_i}$ ) — the strictly increasing sequence itself. You can keep this line empty if $n_i = 0$ (or just print the empty line).

In the fourth line print $n_d$ — the number of elements in the strictly decreasing sequence. $n_d$ can be zero, in this case the decreasing sequence is empty.

In the fifth line print $n_d$ integers $dec_1, dec_2, \dots, dec_{n_d}$ in the decreasing order of its values ( $dec_1 > dec_2 > \dots > dec_{n_d}$ ) — the strictly decreasing sequence itself. You can keep this line empty if $n_d = 0$ (or just print the empty line).

$n_i + n_d$ should be equal to $n$ and the union of printed sequences should be a permutation of the given sequence (in case of "YES" answer).

###Examples

####case 1:
| input |output |
| ------------ | ------------ |
|7 7 2 7 3 3 1 4 |YES 2 3 7 5 7 4 3 2 1 |

####case 2:
| input |output |
| ------------ | ------------ |
|5 4 3 1 5 3 |YES 1 3 4 5 4 3 1 |

####case 3:
| input |output |
| ------------ | ------------ |
|5 1 1 2 1 2 |NO |

####case 4:
| input |output |
| ------------ | ------------ |

|5 0 1 2 3 4 |YES 0 5 4 3 2 1 0 |

###Solve
这是一道1100分的排序题。
官方标签： constructive algorithms sortings

第一行给出数列的长度n
第二行给出长度为n的数列 $a$

问能够将数列a分为单调递增和单调递减的两个数列

如果可以，输出YES，否则输出NO
如果为可以
- 接下来的两行输出递增数列的长度和该递增数列
- 接下来的两个输出递减数列的长度和该递减数列
如果数列的长度为0，则在下一行输出空行
答案不唯一，输出任意正确的答案即可

首先遍历数列 $a$ ，数字 $a[ i ]$ 有以下几种情况

如果 $a[ i ]$ 没有出现过，则加入递增数列
如果 $a[ i ]$ 出现过1次，则加入递减数列
如果 $a[ i ]$ 出现超过2次及2次以上，则无法生成单调递增和单调递减两个数列

#include <bits/stdc++.h>

using namespace std;

int main() {
//    freopen("../in", "r", stdin);
//    freopen("../out", "w", stdout);

    int n;
    vector<int> inc, dec;
    map<int, int> cnt;
    bool found = true;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        cnt[t]++;
        if (cnt[t] == 3)
            found = false;
        if (cnt[t] == 1) {
            inc.push_back(t);
        } else {
            dec.push_back(t);
        }
    }
    sort(inc.begin(), inc.end());
    sort(dec.begin(), dec.end(), greater<int>());
    if (found) {
        cout << "YES" << endl;
        cout << inc.size() << endl;
        for (int i = 0; i < inc.size(); i++) {
            if (i != 0)
                cout << " ";
            cout << inc[i];
        }
        cout << endl << dec.size() << endl;
        for (int i = 0; i < dec.size(); i++) {
            if (i != 0)
                cout << " ";
            cout << dec[i];
        }
        cout << endl;
    } else {
        cout << "NO" << endl;
    }
}

D. Equalize Them All

You are given an array $a$ consisting of $n$ integers. You can perform the following operations arbitrary number of times (possibly, zero):

Choose a pair of indices $(i, j)$ such that $|i-j|=1$ (indices $i$ and $j$ are adjacent) and set $a_i := a_i + |a_i - a_j|$ ;
Choose a pair of indices $(i, j)$ such that $|i-j|=1$ (indices $i$ and $j$ are adjacent) and set $a_i := a_i - |a_i - a_j|$ .

The value $|x|$ means the absolute value of $x$ . For example, $|4| = 4$ , $|-3| = 3$ .

Your task is to find the minimum number of operations required to obtain the array of equal elements and print the order of operations to do it.

It is guaranteed that you always can obtain the array of equal elements using such operations.

Note that after each operation each element of the current array should not exceed $10^{18}$ by absolute value.

###input

The first line of the input contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of elements in $a$ .

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 2 \cdot 10^5$ ), where $a_i$ is the $i$ -th element of $a$ .

###output
In the first line print one integer $k$ — the minimum number of operations required to obtain the array of equal elements.

In the next $k$ lines print operations itself. The $p$ -th operation should be printed as a triple of integers $(t_p, i_p, j_p)$ , where $t_p$ is either $1$ or $2$ ( $1$ means that you perform the operation of the first type, and $2$ means that you perform the operation of the second type), and $i_p$ and $j_p$ are indices of adjacent elements of the array such that $1 \le i_p, j_p \le n$ , $|i_p - j_p| = 1$ . See the examples for better understanding.

Note that after each operation each element of the current array should not exceed $10^{18}$ by absolute value.

If there are many possible answers, you can print any.

###Examples

####case 1:
| input |output |
| ------------ | ------------ |
|5 2 4 6 6 6| 2 1 2 3 1 1 2 |

####case 2:
| input |output |
| ------------ | ------------ |
|3 2 8 10|2 2 2 1 2 3 2|

####case 3:
| input |output |
| ------------ | ------------ |
|4 1 1 1 1 |0|

###Solve
这是一道1400分的题。
官方标签： constructive algorithms greedy

第一行给出数列长度n
第二行给出长度为n的数列 $a$

现在给定两个操作：

选择任意两个相邻的元素，使 $a_i := a_i + |a_i - a_j|$
选择任意两个相邻的元素，使 $a_i := a_i - |a_i - a_j|$

要求可以经过k次操作，使数列 $a$ 中的所有元素都相同。
求k的最小值，并在接下来k行按顺序以操作编号下标i 下标 j的形式输出该操作

题目保证有解。如果有多个解，则输出任一解。

以case1为举例，2 4 6 6 6

i = 2 , j = 3.进行操作1，使 $a[2] = a[3] = 6$ , 当前序列为2 6 6 6 6
i = 1 , j = 2.进行操作1，使 $a[1] = a[2] = 6$ , 当前序列为6 6 6 6 6

首先为了移动次数尽可能的少，求出数列 $a$ 中出现次数最多的数字 $q$ ，并设第一次出现数字 $q$ 的下标设为 $pos$ .
接下来从后到前遍历 $a[pos - 1]$ 到 $a[1]$ 的所有元素, 并将每个元素的值变成该元素之后的一个元素的值。经过这次操作后， $a[pos - 1]$ 到 $a[1]$ 所有元素都等于 $q$ .
最后从前之后遍历整个数列 $a$ ，使值不等于 $q$ 的元素都成为该元素之前的元素的值。经过这次操作后， $a[1]$ 到 $a[n]$ 所有元素都等于 $q$ .

#include <bits/stdc++.h>

using namespace std;

int main() {
//    freopen("../in", "r", stdin);
//    freopen("../out", "w", stdout);

    int n;
    cin >> n;
    vector<int> arr(n), cnt(200000 + 1);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        cnt[arr[i]]++;
    }
    int t = max_element(cnt.begin(), cnt.end()) - cnt.begin();
    int pos = find(arr.begin(), arr.end(), t) - arr.begin();

    cout << n - cnt[t] << endl;
    for (int i = pos - 1; i >= 0; i--) {
        cout << ((arr[i] > arr[i + 1]) ? "2" : "1") << " " << i + 1 << " " << i + 2 << endl;
        arr[i] = arr[i + 1];
    }
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] != arr[i + 1]) {
            cout << ((arr[i] > arr[i + 1] ? "1" : "2")) << " " << i + 2 << " " << i + 1 << endl;
            arr[i + 1] = arr[i];
        }
    }
}

E. Median String

You are given two strings $s$ and $t$ , both consisting of exactly $k$ lowercase Latin letters, $s$ is lexicographically less than $t$ .

Let's consider list of all strings consisting of exactly $k$ lowercase Latin letters, lexicographically not less than $s$ and not greater than $t$ (including $s$ and $t$ ) in lexicographical order. For example, for $k=2$ , $s=$ "az" and $t=$ "bf" the list will be ["az", "ba", "bb", "bc", "bd", "be", "bf"].

Your task is to print the median (the middle element) of this list. For the example above this will be "bc".

It is guaranteed that there is an odd number of strings lexicographically not less than $s$ and not greater than $t$ .

###input

The first line of the input contains one integer $k$ ( $1 \le k \le 2 \cdot 10^5$ ) — the length of strings.

The second line of the input contains one string $s$ consisting of exactly $k$ lowercase Latin letters.

The third line of the input contains one string $t$ consisting of exactly $k$ lowercase Latin letters.

It is guaranteed that $s$ is lexicographically less than $t$ .

It is guaranteed that there is an odd number of strings lexicographically not less than $s$ and not greater than $t$ .

###output
Print one string consisting exactly of $k$ lowercase Latin letters — the median (the middle element) of list of strings of length $k$ lexicographically not less than $s$ and not greater than $t$ .

###Examples

####case 1:
| input |output |
| ------------ | ------------ |
|2 az bf| bc |

####case 2:
| input |output |
| ------------ | ------------ |
|5 afogk asdji|alvuw|

####case 3:
| input |output |
| ------------ | ------------ |
|6 nijfvj tvqhwp |qoztvz|

###Solve
这是一道1900分的题。
官方标签：bitmasks math number theory strings

第一行给出字符串长度k
接下来两行分别给出长度为k的字符串s, t
我们得到所有长度为k的字符串序列，该序列的任一字符串的字典序都大于等于s并小于等于t。

要求输出该序列的最中间的元素。

以case 1为例子：
s = "az" t = "bf"
根据s,t我们可以得到序列["az", "ba", "bb", "bc", "bd", "be", "bf"]
那么处在中间的元素则为bc

题目保证序列的元素个数为奇数，即恰好只存在一个中间元素。

题目看似是一个字符串题目，但是根据题目可以知道这个字符串的长度最长有 $2 \cdot 10^5$ 位，单靠暴力枚举肯定会超时。
我们只需将字符串看成一个26进制数，并用高精度的思想，求得这两个大数的平均数。将平均数转化成对应的字符串。该字符串即为所的答案。

#include <bits/stdc++.h>

using namespace std;

int main() {
//    freopen("../in", "r", stdin);
//    freopen("../out", "w", stdout);

    int n;
    string a, b;
    cin >> n >> a >> b;

    vector<int> num1(n + 1), num2(n + 1), addup(n + 1), divide(n + 1);

    for (int i = 1; i <= n; i++) {
        num1[i] = a[i - 1] - 'a';
        num2[i] = b[i - 1] - 'a';
    }

    int pre = 0;
    for (int i = n; i >= 0; i--) {
        addup[i] = num1[i] + num2[i] + pre;
        if (addup[i] >= 26) {
            pre = 1;
            addup[i] -= 26;
        } else {
            pre = 0;
        }
    }

//    for (int i = 0; i <= n; i++) {
//        cout << addup[i] << " ";
//    }

    pre = 0;
    for (int i = 0; i <= n; i++) {
        pre = pre * 26 + addup[i];
        divide[i] = pre / 2;
        pre = pre % 2;
    }
    for (int i = 1; i <= n; i++) {
        cout << (char) (divide[i] + 'a');
    }

}

F. Graph Without Long Directed Paths

You are given a connected undirected graph consisting of $n$ vertices and $m$ edges. There are no self-loops or multiple edges in the given graph.

You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).

###input

The first line contains two integer numbers $n$ and $m$ ( $2 \le n \le 2 \cdot 10^5$ , $n - 1 \le m \le 2 \cdot 10^5$ ) — the number of vertices and edges, respectively.

The following $m$ lines contain edges: edge $i$ is given as a pair of vertices $u_i$ , $v_i$ ( $1 \le u_i, v_i \le n$ , $u_i \ne v_i$ ). There are no multiple edges in the given graph, i. e. for each pair ( $u_i, v_i$ ) there are no other pairs ( $u_i, v_i$ ) and ( $v_i, u_i$ ) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).

###output
If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print "NO" in the first line.

Otherwise print "YES" in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of '0' and '1') of length $m$ . The $i$ -th element of this string should be '0' if the $i$ -th edge of the graph should be directed from $u_i$ to $v_i$ , and '1' otherwise. Edges are numbered in the order they are given in the input.

###Examples

####case 1:
| input |output |
| ------------ | ------------ |
|6 5 1 5 2 1 1 4 3 1 6 1| YES 10100 |

###Note
The picture corresponding to the first example:

And one of possible answers:

###Solve
这是一道1700分的题。
官方标签：dfs and similar graphs

第一行给出了图中点的个数n和边的条数m
接下来m行给出 $u_i, v_i$ ，表示边

要求你给该无向图的每条边进行定向，是该有向图不包含长度为2或更大的路径（路径长度表示为遍历边的数量）

如果可以，则输出YES。并在第二行按输入的顺序，输出每条边的方向，0表示 $u_i \rightarrow v_i$ ，1表示 $v_i \rightarrow u_i$ 。
如果不可以，则直接输出NO

通过题意，题目要求每个点要么只能有出度，否则只能有入度，每个点只能拥有一种状态。所以通过这个要求，直接给这个图染色即可。

首先从每个点出发，dfs深搜，遍历连接每条边，并给这条边的另一个点染上与自己相反的颜色，如果只有出度则染上颜色0，只有入度则染上颜色1.
如果发现边的另一个点已经染过色并且颜色与自身一样，则无法完成目标，直接输出NO。
最后所有点完成深搜，通过自身的颜色来输出方向即可。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;

const int MAXN = 200000 + 10;

int n, m;

int color[MAXN];
vector<int> G[MAXN];
vector<P> u;
int found = true;

void dfs(int x, int self, int c) {
//    cout << x << " =" << c << endl;
    color[x] = c;
    for (auto v : G[x]) {
        if (v == self)
            continue;
        if (color[v] == -1) {
            dfs(v, x, !c);
        } else if (color[x] == color[v]) {
            found = false;
        }
    }
}

int main() {
//    freopen("../in", "r", stdin);
//    freopen("../out", "w", stdout);


    cin >> n >> m;
    memset(color, -1, sizeof(color));
    for (int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        t1--;
        t2--;
        G[t1].push_back(t2);
        G[t2].push_back(t1);
        u.push_back(P(t1, t2));
    }

    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            dfs(i, -1, 0);
        }
    }
    puts(found ? "Yes" : "No");
    if (found) {
        for (int i = 0; i < m; i++) {
            cout << (color[u[i].first] ? "0" : "1");
        }
    }
}

G. Two Merged Sequences

Two integer sequences existed initially, one of them was strictly increasing, and another one — strictly decreasing.

Elements of increasing sequence were inserted between elements of the decreasing one (and, possibly, before its first element and after its last element) without changing the order. For example, sequences $[1, 3, 4]$ and $[10, 4, 2]$ can produce the following resulting sequences: $[10, \textbf{1}, \textbf{3}, 4, 2, \textbf{4}]$ , $[\textbf{1}, \textbf{3}, \textbf{4}, 10, 4, 2]$ . The following sequence cannot be the result of these insertions: $[\textbf{1}, 10, \textbf{4}, 4, \textbf{3}, 2]$ because the order of elements in the increasing sequence was changed.

Let the obtained sequence be $a$ . This sequence $a$ is given in the input. Your task is to find any two suitable initial sequences. One of them should be strictly increasing, and another one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

If there is a contradiction in the input and it is impossible to split the given sequence $a$ into one increasing sequence and one decreasing sequence, print "NO".

###input

The first line of the input contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of elements in $a$ .

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 2 \cdot 10^5$ ), where $a_i$ is the $i$ -th element of $a$ .

###output
If there is a contradiction in the input and it is impossible to split the given sequence $a$ into one increasing sequence and one decreasing sequence, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line, print a sequence of $n$ integers $res_1, res_2, \dots, res_n$ , where $res_i$ should be either $0$ or $1$ for each $i$ from $1$ to $n$ . The $i$ -th element of this sequence should be $0$ if the $i$ -th element of $a$ belongs to the increasing sequence, and $1$ otherwise. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

###Examples

####case 1:
| input |output |
| ------------ | ------------ |
|9 5 1 3 6 8 2 9 0 10|YES 1 0 0 0 0 1 0 1 0 |

####case 2:
| input |output |
| ------------ | ------------ |
|5 1 2 4 0 2|NO|

###Solve
这是一道2600分的贪心题。
官方标签：dp greedy

题目第一行给出数列长度n
第二行给出长度为n的数列 $a$

问：这个数列能否分成两个数列，这两个数列的相对位置保持不变，使这两个数列一个单调递增，一个单调递减。如果可以，输出YES，并在下一行输出该元素属于上升序列还是下降序列，如果是上升，输出0；如果是下降，输出1。如果不行，则直接输出NO

首先判断 $a[ i ]$ 能否放入递增或递减数列中，如果都不可以则直接输出No。
假如是可以放入的时候，则比较 $a[ i ]$ 与 $a[ i + 1]$ ，如果 $a[ i ] > a[ i + 1 ]$ ，则放入递减数列；反之放入递增数列。如果 $a[ i ] = a[ i + 1 ]$ ，则各方一个。

#include <bits/stdc++.h>

using namespace std;

int main() {
//    freopen("../in", "r", stdin);
//    freopen("../out", "w", stdout);

    int n;
    cin >> n;
    vector<int> arr, inc, dec, cnt(n);

    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        arr.push_back(t);
    }

    for (int i = 0; i < n; i++) {
        bool inc_flag = false;
        bool dec_flag = false;

        if (inc.empty())
            inc_flag = true;
        else {
            inc_flag = (arr[i] > inc[inc.size() - 1]);
        }
        if (dec.empty())
            dec_flag = true;
        else {
            dec_flag = (arr[i] < dec[dec.size() - 1]);
        }
        if (inc_flag && dec_flag) {
            if (i < n - 1 && arr[i + 1] > arr[i]) {
                inc.push_back(arr[i]);
                cnt[i] = 0;
            } else {
                dec.push_back(arr[i]);
                cnt[i] = 1;
            }
        } else if (inc_flag) {
            inc.push_back(arr[i]);
            cnt[i] = 0;
        } else if (dec_flag) {
            dec.push_back(arr[i]);
            cnt[i] = 1;
        } else {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    for (int i = 0; i < n; i++) {
        if (i != 0)cout << " ";
        cout << cnt[i];
    }
}

Codeforces Round #550 (Div.3)

A. Wrong Subtraction

B. Parity Alternated Deletions

C. Two Shuffled Sequences

|5<br>0 1 2 3 4 |YES<br>0<br><br>5<br>4 3 2 1 0 |

D. Equalize Them All

E. Median String

F. Graph Without Long Directed Paths

G. Two Merged Sequences