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 \ne 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 \le N \le 2 \times 10^5~

$0 \le a_i,b_i,c_i,d_i$ ~0 \le 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 \le N-i~

Subtask 1 [12%]

$N \le 7$ ~N \le 7~

Subtask 2 [23%]

$b_i, c_i = 0$ ~b_i, c_i = 0~

Subtask 3 [43%]

$N \le 5 \times 10^3$ ~N \le 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, \ldots, a_N~.

The next line contains $N$ ~N~ integers $b_1, \ldots, b_N$ ~b_1, \ldots, b_N~.

The next line contains $N$ ~N~ integers $c_1, \ldots, c_N$ ~c_1, \ldots, c_N~.

The next line contains $N$ ~N~ integers $d_1, \ldots, d_N$ ~d_1, \ldots, 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

Sample Output

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

11

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

I'm still here...

-2

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

hi still here

1

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

wac7 when