Distinct Pairs

All submissions for this problem are available.
###Read problem statements in [Hindi](http://www.codechef.com/download/translated/JAN19/hindi/DPAIRS.pdf), [Bengali](http://www.codechef.com/download/translated/JAN19/bengali/DPAIRS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JAN19/mandarin/DPAIRS.pdf), [Russian](http://www.codechef.com/download/translated/JAN19/russian/DPAIRS.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JAN19/vietnamese/DPAIRS.pdf) as well. Chef has two integer sequences $A_1, A_2, \ldots, A_N$ and $B_1, B_2, \ldots, B_M$. You should choose $N+M1$ pairs, each in the form $(A_x, B_y)$, such that the sums $A_x + B_y$ are all pairwise distinct. It is guaranteed that under the given constraints, a solution always exists. If there are multiple solutions, you may find any one. ### Input  The first line of the input contains two spaceseparated integers $N$ and $M$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$.  The third line contains $M$ spaceseparated integers $B_1, B_2, \ldots, B_M$. ### Output Print $N+M1$ lines. Each of these lines should contain two spaceseparated integers $x$ and $y$ denoting that you chose a pair $(A_{x+1}, B_{y+1})$. ### Constraints  $1 \le N, M \le 2 \cdot 10^5$  $A_i \le 10^9$ for each valid $i$  $B_i \le 10^9$ for each valid $i$  $A_1, A_2, \ldots, A_N$ are pairwise distinct  $B_1, B_2, \ldots, B_M$ are pairwise distinct ### Subtasks **Subtask #1 (25 points):** $1 \le N, M \le 10^3$ **Subtask #2 (75 points):** original constraints ### Example Input ``` 3 2 10 1 100 4 3 ``` ### Example Output ``` 2 1 0 0 1 0 0 1 ``` ### Explanation The chosen pairs and their sums are:  $A_3 + B_2 = 100+3 = 103$  $A_1 + B_1 = 10+4 = 14$  $A_2 + B_1 = 1+4 = 5$  $A_1 + B_2 = 10+3 = 13$ Since all sums are distinct, this is a correct output.Author:  sanroylozan 
Editorial  https://discuss.codechef.com/problems/DPAIRS 
Tags  datastructure, easy, jan19, observations, sanroylozan, taran_1407 
Date Added:  31122018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions