Hide

Problem H
Pardans

I den lilla staden Dansvik är den årliga pardansfestivalen en av årets största händelser. Människor från hela regionen samlas för att delta i den traditionsenliga dansen, en kväll fylld av musik, glädje och rörelse. Det finns exakt $2N$ personer som har anmält sig till evenemanget, och enligt traditionen ska alla paras ihop i danspar.

Men arrangörerna har stött på ett problem. Under kvällens höjdpunkt planeras ett stort gruppfoto, och för att göra bilden perfekt vill de säkerställa att alla ansikten syns tydligt. För att undvika att någon blir skymd av en längre partner, har arrangörerna bestämt att det måste finnas en viss höjdskillnad, minst $D$ längdenheter, mellan personerna i varje par.

Arrangörerna har listor över alla deltagarnas längder, men nu måste de lösa det logistiska pusslet: är det möjligt att para ihop deltagarna så att höjdskillnaden i varje par är minst $D$? Och om det är möjligt, hur ska paren se ut? Stressade men hoppfulla kämpar de för att hitta en lösning innan kvällen är över.

Indata

Den första raden indata består av två heltal $N$ och $D$ ($1 \leq N \leq 2 \cdot 10^5$, $0 \leq D \leq 10^9$), antal par av personer som kommer bildas respektive minsta avståndet tillåtet i ett par.

Den andra och sista raden innehåller $2N$ heltal $l_i$ ($0 \leq i < 2N, 0 \leq l_i \leq 10^9$), där $l_i$ är längden på person index $i$.

Utdata

För att få $50\% $ av poängen ska programmet endast skriva ut en sträng: ”Ja” ifall det finns en giltig parning, annars ”Nej”.

För att få full poäng krävs det att du skriver ut $N$ ytterligare rader ifall svaret är ”Ja”. Av dessa ytterligare $N$ raderna ska varje rad bestå av 2 heltal, där heltalen på samma rad ska representera längderna av personerna som paras ihop.

De $N$ paren av tal programmet skriver ut måste då vara samma $2N$ tal som i indatan. Höjdskillnaden inom varje par måste också vara minst $D$. Om parningen är ogiltig (till exempel om programmet inte skriver ut exakt $2N$ tal, talen inte stämmer med indatan, eller höjdskillnaden inom något par är mindre än $D$), kommer det räknas som att du har fel på hela det testfallet.

Ifall ditt program skriver ut ”Nej” ska ditt program avslutas direkt.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

För varje testgrupp, ifall ditt program endast skriver ut korrekt svarar på om det finns en giltig parning eller inte, så får du $50\% $ av testgruppens poäng.

För att få alla poäng i en testgrupp behöver programmet skriva ut en giltig parning.

Grupp

Poängvärde

Begränsningar

$1$

$20$

$N \leq 4$

$2$

$40$

$N \leq 1000$

$3$

$40$

Inga ytterligare begränsningar.

Förklaring av exempelfall 1

En möjlig lösning är att para ihop personen med längd 120 tillsammans med längd 110, samt personen med längd 160 tillsammans med längd 150. Skillnaden i varje par är då exakt 10, vilket är giltigt. Ifall endast ”Ja” skrivs ut, skulle lösningen endast få 50 poäng.

\includegraphics[width=0.5\textwidth ]{pardans.png}

Förklaring av exempelfall 2

Eftersom alla personer har samma längd, innebär det att det är omöjligt att para ihop personerna så att skillnaden mellan 2 personer är minst 30.

Sample Input 1 Sample Output 1
2 10
120 110 160 150
Ja
120 110
160 150
Sample Input 2 Sample Output 2
3 30
1 1 1 1 1 1
Nej
Sample Input 3 Sample Output 3
5 10
12 18 24 18 42 30 24 30 12 24
Ja
24 12
30 18
12 24
30 18
24 42
Sample Input 4 Sample Output 4
1 0
5 5
Ja
5 5

Please log in to submit a solution to this problem

Log in