34957번 - 맥스웰의 수수께끼 악마 서브태스크스페셜 저지

문제

승민이는 ”맥스웰의 수수께끼 악마”라는 열역학에 기반한 흥미로운 퍼즐 게임을 하고 있다. 하지만 어려운 퍼즐에 절망한 승민이는 결국 퍼즐을 해결하는 것을 포기하고 말았다. 승민이를 도와 퍼즐을 해결해 보자!

현재 $N$개의 블록들이 일렬로 놓여있다. 각각의 블록 $B_i$는 고유한 온도 $T_i$와 크기 $S_i$를 가진다. 온도에는 고온, 상온, 저온이 존재하며, 각 블록은 오직 하나의 온도를 가진다. 이때, 당신은 연속된 몇 개의 블록을 골라 블록들끼리 서로 접촉시킬 수 있으며, 접촉한 블록들끼리 열교환이 일어나 이 블록들은 모두 같은 온도로 변한다.

열교환은 아래와 같은 과정으로 이루어진다.

1. 일렬로 놓인 블록들 중 연속한 몇 개의 블록 $B_s,ドル $B_{s+1},ドル $\cdots,ドル $B_e$로 이루어진 구간을 하나 선택한다.
2. 구간에 속한 블록들 중 저온인 블록의 크기 합이 고온인 블록의 크기 합보다 크다면 모든 블록이 저온으로 변하고, 저온인 블록의 크기 합이 고온인 블록의 크기 합보다 작다면 모든 블록이 고온으로 변한다. 두 값이 서로 같다면 모든 블록이 상온으로 변한다.

당신의 목표는 이 블록들에 열교환을 원하는 만큼 시행해 모든 블록을 저온으로 만드는 것이다. 입력으로 블록들의 상태가 주어졌을 때, 열교환을 적절하게 진행하여 모든 블록을 저온으로 만드는 방법을 하나 찾아보자.

입력

첫째 줄에 총 블록의 수 $N$이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 블록들의 정보가 주어진다. $i+1$번째 줄에는 $i$번째 블록의 $T_i$와 $S_i$가 공백으로 구분되어 주어진다. $T_i$는 블록이 고온, 상온, 저온일 때 차례대로 1ドル,ドル 0ドル,ドル $-1$의 값을 가진다.

출력

모든 블록을 저온으로 만들 수 있다면, 첫째 줄에 모든 블록을 저온으로 만들기 위해 진행할 접촉 횟수 $M$ (0ドル\le M\le N$)을 출력한다. 이 경우 0ドル \le M \le N$인 방법이 항상 존재함이 보장된다.

둘째 줄부터 $M$개의 줄에 걸쳐 열교환을 진행할 순서대로 선택한 구간의 양 끝 블록의 번호 $s$와 $e$ $(1\le s\le e\le N)$를 공백으로 구분하여 출력한다. 가능한 방법이 여러 개여도 하나만 출력하면 된다.

만일 모든 블록을 저온으로 만드는 것이 불가능하다면, 첫째 줄에 -1을 출력한다.

제한

• 1ドル \le N \le 200\ 000$
• $T_{i} \in \{-1, 0, 1\}$
• 1ドル \le S_{i} \le 10^9$

서브태스크

노트

☆★맥☆스☆웰☆의☆수☆수☆께☆끼☆악☆마★☆
☞지☆금☆당☆장☆구☆매☜
https://store.steampowered.com/app/2770160