DMOPC '20 Contest 6 P2 - Interpretive Art - Olympiads Online Judge

DMOPC '20 Contest 6 P2 - Interpretive Art

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$ $A$ (consisting of only $0$ $0$ s and $1$ $1$ s) of length $N$ $N$ , and she wants to turn it into some beautiful binary array $B$ $B$ of the same length. To do this, she borrowed a magical brush from Senpai. With one stroke of the brush from index $l$ $l$ to index $r$ $r$ , she can rearrange the numbers from index $l$ $l$ to index $r$ $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$ $A$ into $B$ $B$ , as well as a minimal sequence of strokes that accomplishes this task.

Constraints

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

$A_i, B_i \in \{0, 1\}$ $A_{i}, B_{i} \in {0, 1}$

Subtask 1 [40%]

$1 \le N \le 2 \times 10^3$ $1 \leq N \leq 2 \times 10^{3}$

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains an integer $N$ $N$ .

The second line contains $N$ $N$ integers $A_i$ $A_{i}$ $(1 \le i \le N)$ $(1 \leq i \leq N)$ , representing the array $A$ $A$ .

The third line contains $N$ $N$ integers $B_i$ $B_{i}$ $(1 \le i \le N)$ $(1 \leq i \leq N)$ , representing the array $B$ $B$ .

Output Specification

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

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

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

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

Sample Input 1

Copy

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

Sample Output 1

Copy

2
5 7
1 5

Explanation for Sample 1

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

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

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

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

Sample Input 2

Copy

3
1 0 1
0 1 0

Sample Output 2

Copy

-1

Comments

There are no comments at the moment.