아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Baka bullar

시간 제한1초메모리 제한1024 MB

요약
서로 다른 위치 N개와 폭 D가 주어질 때, 구간 뒤집기를 최대 100000번 사용해 모든 항목을 연속한 N개 좌표에 모으는 방법을 찾거나 불가능하다고 판정하는 문제입니다.
난이도

보통10점 중 6점

유형
그리디, 시뮬레이션, 수학, 구현
정답자
아직 제출이 없습니다

문제

Du har bakat bullar och lagt dem på en lång rad. Totalt har du NN bullar, där den ii:te finns på xx-koordinat x_ix\_i. Du skulle vilja samla ihop bullarna så att de ligger bredvid varandra, alltså på koordinater a,a+1,a+2,…,a+N−1a, a+1, a+2, \dots, a+N-1 för något aa. Men bullarna är väldigt varma och kan endast hanteras med hjälp av en spade med bredd DD. I ett drag kan du välja ett intervall av längd DD och vända på alla bullar i det intervallet. Mer specifikt kan du välja ett intervall på formen \[L,L+D−1]\[L, L+D-1]. En bulle vars xx-koordinat uppfyller L≤x_i≤L+D−1L \leq x\_i \leq L+D-1 flyttas då till xx-koordinat L+D−1−(x_i−L)L + D - 1 - (x\_i - L).

Du får givet de NN bullarnas positioner och talet DD. Din uppgift är att hitta en sekvens av drag så att bullarna hamnar bredvid varandra. Du får använda högst 10510^5 drag.

입력

Den första raden innehåller två heltal NN och DD (2≤N,D≤2002 \leq N, D \leq 200).

Den andra raden innehåller NN heltal x_ix\_i (1≤x_i≤2001 \leq x\_i \leq 200). Alla talen x_ix\_i är olika.

출력

Om det inte finns någon lösning, skriv ut "-1".

Annars, skriv först ut en rad med heltalet MM (0≤M≤1050 \leq M \leq 10^5), antalet drag. Skriv därefter ut MM rader, där den ii:te innehåller heltalet L_iL\_i.

Detta innebär att det ii:te draget vänder på intervallet \[L_i,L_i+D−1]\[L\_i, L\_i + D - 1]. Talet L_iL\_i får vara nästan\footnote{Heltalet måste uppfylla −2147483648≤L_i≤2147483647-2147483648 \leq L\_i \leq 2147483647, annars får du fel svar.} vilket heltal som helst, inklusive negativt. Lösningen räknas som korrekt om bullarna ligger bredvid varandra efter att samtliga drag utförts. Ordningen på bullarna spelar ingen roll.

예제2

  1. 예제 1

    입력
    4 4
    1 7 2 8
    
    예상 출력
    2
    1
    5
    
  2. 예제 2

    입력
    4 5
    1 2 3 5
    
    예상 출력
    -1