The Contest Contest 1 P3 - A Typical WAC Problem - Olympiads Online Judge

The Contest Contest 1 P3 - A Typical WAC Problem

Points: 15 (partial)

Time limit: 1.5s

Memory limit: 256M

Author:

Problem types

After his leave from DMOJ, Wesley is very angry and demands you to construct an array $x$ $x$ of length $N$ $N$ consisting of positive integers such that each element $x_i$ $x_{i}$ satisfies the following requirements:

There are $a_i$ $a_{i}$ elements before index $i$ $i$ that are strictly smaller than $x_i$ $x_{i}$
There are $b_i$ $b_{i}$ elements after index $i$ $i$ that are strictly smaller than $x_i$ $x_{i}$
There are $c_i$ $c_{i}$ elements before index $i$ $i$ that are strictly greater than $x_i$ $x_{i}$
There are $d_i$ $d_{i}$ elements after index $i$ $i$ that are strictly greater than $x_i$ $x_{i}$

Luckily, Wesley is a kind person and will allow for your array to violate at most $1$ $1$ of the requirements above. In particular, you can pick an index $i$ $i$ and modify exactly one of $a_i$ $a_{i}$ , $b_i$ $b_{i}$ , $c_i$ $c_{i}$ and $d_i$ $d_{i}$ . In exchange however, he requests that your array is the lexicographically least one (it must be the lexicographically least array that violates at most $1$ $1$ requirement).

Note: We say that array $x$ $x$ is lexicographically less than array $y$ $y$ if $x \ne y$ $x \neq y$ and at the smallest index $i$ $i$ where $x_i$ $x_{i}$ and $y_i$ $y_{i}$ differ, $x_i < y_i$ $x_{i} < y_{i}$ .

Constraints

$2 \le N \le 2 \times 10^5$ $2 \leq N \leq 2 \times 10^{5}$

$0 \le a_i,b_i,c_i,d_i$ $0 \leq a_{i}, b_{i}, c_{i}, d_{i}$

$a_i+c_i < i$ $a_{i} + c_{i} < i$

$b_i+d_i \le N-i$ $b_{i} + d_{i} \leq N - i$

Subtask 1 [12%]

$N \le 7$ $N \leq 7$

Subtask 2 [23%]

$b_i, c_i = 0$ $b_{i}, c_{i} = 0$

Subtask 3 [43%]

$N \le 5 \times 10^3$ $N \leq 5 \times 10^{3}$

Subtask 4 [22%]

No additional constraints.

Input Specification

The first line contains a single integer $N$ $N$ .

The next line contains $N$ $N$ integers $a_1, \ldots, a_N$ $a_{1}, \dots, a_{N}$ .

The next line contains $N$ $N$ integers $b_1, \ldots, b_N$ $b_{1}, \dots, b_{N}$ .

The next line contains $N$ $N$ integers $c_1, \ldots, c_N$ $c_{1}, \dots, c_{N}$ .

The next line contains $N$ $N$ integers $d_1, \ldots, d_N$ $d_{1}, \dots, d_{N}$ .

Output Specification

If no such array exists, output -1.

Otherwise, output the elements of the lexicographically least array on a single line.

Sample Input

Copy

Sample Output

Copy

2 1 4 3 2

Explanation for Sample

The array above satisfies all the requirements except for $d_2$ $d_{2}$ . It can be shown that this is the lexicographically least array that violates at most one requirement.

Comments

12

wleung_bvg commented on Feb. 20, 2024, 10:51 a.m.

I'm still here...

-3

thomas_li commented on Feb. 20, 2024, 5:34 p.m.

hi still here

2

volcano commented on Feb. 20, 2024, 3:04 p.m.

wac7 when