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

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

거짓말

면접 대비

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

요약
각 사람이 거짓말을 하는 사람 수의 하한 또는 상한을 말할 때, 모든 주장과 모순되지 않는 거짓말쟁이 수를 모두 구한다.
난이도

보통10점 중 4점

유형
배열, 누적 합, 구현
정답자
아직 제출이 없습니다

문제

당신 앞에는 NN명의 사람들이 있다. 각 사람은 자신을 포함하여 몇 명 이상이 거짓말을 하고 있다고 말하거나, 몇 명 이하의 사람이 거짓말을 하고 있다고 말한다.

예를 들어, 각 사람이 다음과 같이 주장한다고 하자.

  • 첫 번째 사람이 이렇게 말한다: "1명 이상이 거짓말을 하고 있다!"
  • 두 번째와 세 번째 사람이 이렇게 말한다: "1명 이하가 거짓말을 하고 있다!"
  • 네 번째 사람이 이렇게 말한다: "2명 이상이 거짓말을 하고 있다!"

이 경우에 가능한 시나리오는 다음과 같다.

  • 네 번째 사람만 거짓말을 하고 있다.
  • 두 번째와 세 번째 사람이 거짓말을 하고 있다.

사람들의 주장이 주어질 때, 거짓말을 하는 사람의 수로 가능한 것을 모두 구해라.

입력

첫째 줄에 사람의 수 NN이 주어진다.

둘째 줄에 NN개의 정수 k_1,⋯ ,k_Nk\_1,\cdots ,k\_N이 공백을 사이에 두고 주어진다.

  • k_ik\_i가 양의 정수라면, ii번째 사람이 "k_ik\_i명 이상이 거짓말을 하고 있다"고 말했다는 뜻이다.
  • k_ik\_i가 0이거나 음의 정수라면, ii번째 사람이 "−k_i-k\_i명 이하가 거짓말을 하고 있다"고 말했다는 뜻이다.

출력

첫째 줄에 거짓말을 하는 사람의 수로 가능한 수의 개수를 출력한다.

둘째 줄에 가능한 수들을 공백을 사이에 두고 오름차순으로 출력한다.

제한

  • 1≤N≤500,0001\leq N\leq 500\\, 000
  • −N≤k_i≤N-N\le k\_i\le N (1≤i≤N1\le i\le N)

예제2

  1. 예제 1

    입력
    4
    1 -1 -1 2
    
    예상 출력
    2
    1 2
    
  2. 예제 2

    입력
    1
    0
    
    예상 출력
    2
    0 1