Repovive
  • Dashboard
  • Ranking
  • Submissions
  • Discussion
  1. Contests
  2. Weekly Challenge 1: Approximation
  3. W1D4B

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D4B. Almost Rainbow Permutation (Hard Version)

2 pts·3s·256 MB

Constraints

Input

Output

Samples

Input
5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
Explanation
Output
3
1 1
2 2
3 3

You are given an n×nn \times nn×n matrix aaa. Every element of the matrix is an integer between 111 and nnn.

It is guaranteed that there exists a permutation p1,p2,…,pnp_1, p_2, \ldots, p_np1​,p2​,…,pn​ such that the values

a1,p1,a2,p2,…,an,pna_{1,p_1}, a_{2,p_2}, \ldots, a_{n,p_n}a1,p1​​,a2,p2​​,…,an,pn​​

are pairwise distinct.

Choose at least ⌈n2⌉\left\lceil \frac{n}{2} \right\rceil⌈2n​⌉ cells of the matrix such that:

  • no two chosen cells are in the same row;
  • no two chosen cells are in the same column;
  • no two chosen cells contain the same value.

It can be proven that such a choice always exists.

  • 1≤n≤6001 \le n \le 6001≤n≤600
  • 1≤ai,j≤n1 \le a_{i,j} \le n1≤ai,j​≤n
  • There exists a permutation p1,p2,…,pnp_1, p_2, \ldots, p_np1​,p2​,…,pn​ such that a1,p1,a2,p2,…,an,pna_{1,p_1}, a_{2,p_2}, \ldots, a_{n,p_n}a1,p1​​,a2,p2​​,…,an,pn​​ are pairwise distinct
nnn a1,1a1,2⋯a1,na2,1a2,2⋯a2,n⋮⋮⋱⋮an,1an,2⋯an,n\begin{array}{cccc} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \end{array}a1,1​a2,1​⋮an,1​​a1,2​a2,2​⋮an,2​​⋯⋯⋱⋯​a1,n​a2,n​⋮an,n​​

First, output an integer kkk, the number of chosen cells.

Then output kkk pairs. The iii-th pair ri,cir_i, c_iri​,ci​ denotes that the cell in row rir_iri​ and column cic_ici​ is chosen.

If there are several valid answers, output any of them.

kr1c1r2c2⋮rkck\begin{array}{l} k \\ r_1 \quad c_1 \\ r_2 \quad c_2 \\ \vdots \\ r_k \quad c_k \end{array}kr1​c1​r2​c2​⋮rk​ck​​

The cells (1,1)(1,1)(1,1), (2,2)(2,2)(2,2), and (3,3)(3,3)(3,3) contain the distinct values 111, 333, and 555. They also use different rows and different columns, so the output is valid.