스마트 홈 온도 기록 정제

문제

스마트 홈의 데이터 수집기는 여러 온도 센서가 보낸 측정 기록을 하나의 파일에 모은다. 통신 지연 때문에 기록이 측정 시각 순서대로 도착하지 않을 수 있고, 같은 센서가 같은 시각의 측정값을 다시 보내기도 한다. 분석에 사용할 파일에는 센서마다 신뢰할 수 있는 최신 기록 하나만 남겨야 한다. 각 기록에는 센서 번호, 측정 시각, 정수 온도, 검사 표시가 들어 있다. 검사 표시가 1이고 온도가 영하 40도 이상 영상 85도 이하일 때만 유효한 기록이다. 두 조건 중 하나라도 만족하지 않으면 무효한 기록으로 버린다. 온도가 범위 안에 있더라도 검사 표시가 0이면 사용할 수 없다. 무효한 기록은 다른 기록을 지우거나 덮어쓰지 않는다. 각 센서에 대해 유효한 기록만 모은 뒤 측정 시각이 가장 큰 기록을 선택한다. 가장 큰 측정 시각을 가진 유효한 기록이 여러 개라면 입력에서 더 뒤에 나온 기록을 선택한다. 이는 같은 시각의 값을 나중에 다시 전송한 경우를 수정본으로 취급하기 때문이다. 측정 시각이 더 작은 기록은 입력에서 나중에 나왔더라도 최신 기록을 대신할 수 없다. 한 번도 유효한 기록을 보내지 않은 센서는 결과에 포함하지 않는다. 입력에 등장하지 않은 센서 역시 출력하지 않는다. 정제 결과를 사용하는 장치가 센서 번호로 자료를 찾을 수 있도록, 선택된 기록들을 센서 번호가 작은 순서대로 출력한다. 선택된 기록의 온도는 변환하거나 평균을 내지 않고 입력된 정수 그대로 유지한다.

입력

첫째 줄에 기록 수를 나타내는 정수 N이 주어진다. 1≤N≤20,000이다.
다음 N개 줄에 센서 번호 d, 측정 시각 t, 온도 v, 검사 표시 q가 공백으로 구분되어 주어진다. 모두 정수이며 1≤d≤1,000, 0≤t≤99,999, -999≤v≤999, q∈{0,1}이다. 입력에서 뒤에 나온 기록이란 줄 번호가 더 큰 기록을 뜻한다.

출력

첫째 줄에 선택된 기록의 수 M을 출력한다. 다음 M개 줄에 선택된 기록의 센서 번호, 측정 시각, 온도를 공백으로 구분하여 센서 번호의 오름차순으로 출력한다. 유효한 기록이 하나도 없으면 0만 출력한다.

7
2 10 20 1
1 8 -41 1
2 9 30 1
1 4 0 0
2 10 21 1
3 0 -40 1
3 2 86 1

2
2 10 21
3 0 -40

3
1 0 20 0
2 1 -41 1
2 2 86 1

0

출처: Devin.KR 자체 제작