DMOPC '20 Contest 6 P2 - Interpretive Art

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Nagatoro is practising some form of interpretive art. She currently has a canvas with a binary array A (consisting of only 0s and 1s) of length N, and she wants to turn it into some beautiful binary array B of the same length. To do this, she borrowed a magical brush from Senpai. With one stroke of the brush from index l to index r, she can rearrange the numbers from index l to index r in non-decreasing order. Due to the minimalistic requirements of modern art, she would like to use the least number of brush strokes possible. Please help her find the minimum number of brush strokes to turn A into B, as well as a minimal sequence of strokes that accomplishes this task.

Constraints

1 \le N \le 5 \times 10^5

A_i, B_i \in \{0, 1\}

Subtask 1 [40%]

1 \le N \le 2 \times 10^3

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains an integer N.

The second line contains N integers A_i (1 \le i \le N), representing the array A.

The third line contains N integers B_i (1 \le i \le N), representing the array B.

Output Specification

If it is impossible to turn A into B, output -1.

Otherwise, on the first line output an integer M, the minimum number of brush strokes to turn A into B.

Then, on the j-th of the next M lines, output 2 integers l_j and r_j (1 \le l_j \le r_j \le N), representing that the j-th brush stroke in your solution goes from index l_j to index r_j.

The array A after applying the M brush strokes in order should satisfy A_i = B_i for all i. If there are multiple possible outputs satisfying these requirements, any of them will be accepted.

Sample Input 1

7
0 1 0 1 0 1 0
0 0 0 1 1 0 1

Sample Output 1

2
5 7
1 5

Explanation for Sample 1

Initially, A is [0, 1, 0, 1, 0, 1, 0].

After the first brush stroke, A becomes [0, 1, 0, 1, 0, 0, 1].

After the second brush stroke, A becomes [0, 0, 0, 1, 1, 0, 1].

This is a valid output since A_i = B_i for all i after the given brush strokes, and it can be proven that 2 is the minimum number of brush strokes possible.

Sample Input 2

3
1 0 1
0 1 0

Sample Output 2

-1

Comments

There are no comments at the moment.