Placeholder

#6172

쿠키 1초 1024MB

문제

정올이는 쿠키를 만드는 것을 좋아한다. 그는 N 종류의 쿠키를 만들었다. 그는 i 번째 종류의 쿠키를 A_i개 만들었다 (1≤i≤N). 그가 만든 쿠키를 팔기 위해서 쿠키를 상자에 담을 것이다. 하지만, 다음과 같은 조건들이 충족되어야 한다.

  • 모든 상자에 대해서 그 상자에 들어있는 쿠키의 종류들은 서로 다르다.

  • 모든 상자에 대해서 그 상자에 들어있는 쿠키의 개수는 다음 M개의 숫자 중 하나와 같다: B_1,B_2,\dots,B_M.

정올이가 만든 쿠키의 정보와 쿠키를 상자에 담는 조건들이 주어졌을 때, 모든 쿠키를 상자에 담을 수 있는지 판단하는 프로그램을 작성하라. 또한, 모든 쿠키를 상자에 담을 수 있다면 최소한의 상자 개수로 쿠키를 담는 방법을 출력하라.


입력

다음 형태의 데이터가 표준 입력으로 주어진다.


NN

A1A_1 A2A_2 \cdots ANA_N

MM

B1B_1 B2B_2 \cdots BMB_M


제한

  • 1N150001 ≤ N ≤ 15\,000

  • Ai1A_i ≥ 1 (1iN)(1 ≤ i ≤ N)

  • A1+A2++AN15000A_1 + A_2 + \cdots + A_N ≤ 15\,000

  • 1MN1 ≤ M ≤ N

  • 1BjN1 ≤ B_j ≤ N (1jM)(1 ≤ j ≤ M)

  • Bj<Bj+1B_j < B_{j+1} (1jM1)(1 ≤ j ≤ M - 1)

  • 주어진 값들은 모두 정수이다.


출력

모든 쿠키를 상자에 담을 수 있고 조건들이 충족된다면 사용된 상자의 개수를 xx라 하고, kk번째 상자에 들어있는 쿠키의 개수를 ckc_k라 하고, kk번째 상자에 들어있는 쿠키의 종류들을 vk,1,vk,2,,vk,ckv_{k,1},v_{k,2},…,v_{k,c_k​}라 하자. 이러한 숫자들을 다음과 같은 형식으로 출력하라.


xx

c1c_1 v1,1v_{1,1} v1,2v_{1,2} \cdots v1,c1v_{1,c_1}

c2c_2 v2,1v_{2,1} v2,2v_{2,2} \cdots v2,c2v_{2,c_2}

\vdots

cxc_x vx,1v_{x,1} vx,2v_{x,2} \cdots vx,cxv_{x,c_x}


사용된 상자의 개수 xx는 최소한의 개수여야 한다. 조건들을 충족하면서 쿠키를 상자에 담는 방법이 여러 가지 있다면 그 중 아무거나 하나를 출력해도 된다.

모든 쿠키를 상자에 담을 수 없거나 조건들이 충족되지 않는다면 -1을 출력하라.


부분문제

번호 점수 조건
#16점
  • N500N ≤ 500, Ai=1A_i = 1 (1iN)(1 ≤ i ≤ N)

#27점
  •   N500N ≤ 500, M=1M = 1

#312점
  • A1+A2++AN15A_1 + A_2 + \cdots + A_N ≤ 15

#445점
  • A1+A2++AN500A_1 + A_2 + \cdots + A_N ≤ 500

#515점
  • A1+A2++AN3 000A_1 + A_2 + \cdots + A_N ≤ 3\ 000

#615점
  • 추가 제한 조건이 없다.


예제1

입력
7
1 1 1 1 1 1 1
3
1 2 3
출력
3
2 1 7
2 2 6
3 3 4 5

이 예제 입력에서, 77개의 쿠키를 33개의 상자에 담을 수 있고 조건들이 충족된다. 다음과 같이 쿠키를 담으면 된다.

  • 쿠키의 종류가 1,71,7 인 쿠키들을 첫 번째 상자에 담는다. 각 종류의 쿠키를 한 개씩 담는다.

  • 쿠키의 종류가 2,62,6 인 쿠키들을 두 번째 상자에 담는다. 각 종류의 쿠키를 한 개씩 담는다.

  • 쿠키의 종류가 3,4,53,4,5 인 쿠키들을 세 번째 상자에 담는다. 각 종류의 쿠키를 한 개씩 담는다.

프로그램이 위와 같이 쿠키를 담는 방법을 출력하면 정답으로 인정된다. 왜냐하면, 77개의 쿠키를 22개 이하의 상자에 담으며 조건들이 충족되는 방법은 없기 때문이다. 조건을 충족하면서 쿠키를 담는 방법은 여러 가지가 있을 수 있다.

이 예제 입력은 서브태스크 1, 3, 4, 5, 6의 제한을 충족한다.


예제2

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

이 예제 입력에서는 조건을 충족하는 것이 불가능하다. 따라서 -1을 출력한다.

이 예제 입력은 서브태스크 2, 3, 4, 5, 6의 제한을 충족한다.


예제3

입력
7
5 4 4 2 1 1 1
2
2 6
출력
7
6 1 2 3 4 5 6
2 2 1
2 3 1
2 4 1
2 7 1
2 3 2
2 3 2

이 예제 입력은 서브태스크 4, 5, 6의 제한을 충족한다.


출처

JOI 2022/2023 Spring Training Camp


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.