편지 최적화

$N$명으로 구성된 프로그래밍 올림피아드 위원회는 예선 포스터가 든 봉투를 모든 학교에 보내려고 한다. 과정을 더 빠르게 하기 위해 해야 할 작업을 분담했다. 작업에는 주소 쓰기, 우표 붙이기, 포스터 넣기, 봉투 닫기 등이 있다. 한 사람이 봉투 하나의 작업을 끝내면 다른 사람에게 전달한다. 작업은 기대했던 만큼 빠르게 진행되지 않았고, 그래서 이들은 누가 더 빠르게 일할 수 있는지 궁금해한다.

각 사람 $p$에게는 초당 $M_p$개의 봉투라는 고유한 최대 생산 속도가 있다. 초당 사람 $p$에게 전달되는 봉투 수를 $I_p$, 그 사람이 초당 작업을 끝내는 봉투 수를 $U_p$라고 하면 $U_p = \min(I_p, M_p)$이다. 즉, 작업할 봉투를 더 많이 받더라도 한 사람이 초당 작업을 끝내는 편지는 $M_p$개를 넘지 않는다. 또한 각 사람에게는 자신이 작업을 끝낸 봉투를 보내는 사람들이 몇 명 있다. 각 사람에게 같은 수의 봉투를 보낼 필요는 없으며, 각 사람은 $p$이 보내는 봉투 중 일정 비율을 받는다. 아무도 봉투를 보내지 않아 생산 라인의 시작점에 있는 사람들은 $I_p = \infty$이고, 따라서 $U_p = M_p$이다(이들에게는 가져갈 수 있는 봉투가 무한히 쌓여 있다). 어떤 사람들은 봉투를 전혀 전달하지 않고, 작업을 끝내면 자기 옆에 쌓아 둘 뿐이다.

어떤 사람들에 대해 $U_p = M_p$이 성립하는가? 즉, 누가 자신의 최대 생산 속도로 일하는가?

채점

여러 테스트 케이스 그룹으로 여러분의 해답을 테스트한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$12$| 각 사람은 최대 한 사람에게 편지를 보내고(즉, $k \leq 1$) 최대 한 사람에게서 편지를 받는다

$2$ |$17$| 아무에게서도 편지를 받지 않는 사람 $1$을 제외하면 각 사람은 정확히 한 명의 다른 사람에게서 편지를 받는다

$3$ |$21$| 사람 $i$이 사람 $j$에게 보낸다면 $i < j$이다

$4$ |$25$| $N, S \le 10$

$5$ |$25$| 추가 제한 없음.

첫 번째 줄에는 사람 수를 나타내는 정수 $N$이 주어진다($1 \le N \le 10^5$). 다음 $N$개의 줄은 사람들을 설명한다. $i$번째 줄에는 먼저 사람 $i$의 최대 생산 속도를 나타내는 정수 $M_i$가 주어진다($1 \le M_i \le 10^5$). 그다음 정수 $k$이 주어지고, 이어서 정수 쌍 $j$ $w$가 $k$개 주어진다. 이는 사람 $i$이 자신의 봉투 중 $w$퍼센트를 사람 $j$에게 보낸다는 뜻이다($1 \le w \le 100$, $1 \le j \le N, i \neq j$). 주어진 한 줄에서 같은 $j$이 두 번 이상 등장할 수 없으며, $k = 0$이 아닌 한 그 줄의 $w$들의 합은 $100$이다.

모든 $k$의 합을 $S$이라고 하자. 그러면 $0 \le S \le 10^5$이 성립한다.

생산 체인은 어떤 사람도 자신이 이미 작업했던 편지를 되돌려 받지 않도록 설계되어 있다.

$U_p = M_p$을 충족하는 모든 $i$을 오름차순으로 한 줄에 출력한다.

$U_p = M_p$이면 이것이 여유를 두고 성립하며, 더 구체적으로는 $I_p - M_p > 10^{-4}$임이 보장된다. 반대로 $U_p \neq M_p$이면 반대 방향으로 여유가 있으며, $M_p - I_p > 10^{-4}$이다.

다음은 세 예제 테스트 케이스를 나타내는 세 그래프이다. 각 사람은 정점 하나로 표현된다. 각 간선에는 전송되는 봉투의 양이 초당 봉투 수 단위로 표시되어 있다.

테스트 케이스 그룹 $1$에서는 예제 $1$만 나올 수 있고, 테스트 케이스 그룹 $2$에서는 예제 $2$만 나올 수 있으며, 테스트 케이스 그룹 $3$에서는 예제 $3$만 나올 수 있음에 유의하라. 테스트 케이스 그룹 $4$과 $5$에서는 세 예제 테스트 케이스가 모두 나올 수 있다.

예제 $1$

예제 $2$

예제 $3$