The Contest Contest 1 P3 - A Typical WAC Problem

View as PDF

Submit solution


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 of length N consisting of positive integers such that each element xi satisfies the following requirements:

  • There are ai elements before index i that are strictly smaller than xi
  • There are bi elements after index i that are strictly smaller than xi
  • There are ci elements before index i that are strictly greater than xi
  • There are di elements after index i that are strictly greater than xi

Luckily, Wesley is a kind person and will allow for your array to violate at most 1 of the requirements above. In particular, you can pick an index i and modify exactly one of ai, bi, ci and di. 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 requirement).

Note: We say that array x is lexicographically less than array y if xy and at the smallest index i where xi and yi differ, xi<yi.

Constraints

2N2×105

0ai,bi,ci,di

ai+ci<i

bi+diNi

Subtask 1 [12%]

N7

Subtask 2 [23%]

bi,ci=0

Subtask 3 [43%]

N5×103

Subtask 4 [22%]

No additional constraints.

Input Specification

The first line contains a single integer N.

The next line contains N integers a1,,aN.

The next line contains N integers b1,,bN.

The next line contains N integers c1,,cN.

The next line contains N integers d1,,dN.

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
5
0 0 2 2 1
1 0 2 1 0
0 1 0 1 2
2 1 0 0 0

Sample Output

Copy
2 1 4 3 2

Explanation for Sample

The array above satisfies all the requirements except for d2. 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