5461번 - 고용 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 556 | 119 | 95 | 20.652% |
문제
재현이는 초고층 건물인 "제2사과타워"를 짓기 위해 노동자들을 고용하고 있다. 1번부터 N번까지 총 N명의 노동자들이 지원했는데, i (1 ≤ i ≤ N)번째 노동자는 최저임금 Si를 가지고 있어 Si보다 크거나 같은 만큼의 임금을 받아야 하며, 또한 Qi라는 건설 자격증 레벨을 가지고 있다.
최근 정부에서는 건설 자격증을 활성화하기 위해서, 노동자들의 임금을 항상 자격증 레벨에 비례하기 지급하게 하는 규정을 만들었다. 만약 A라는 노동자의 자격증 레벨이 Qa이고, B라는 노동자의 자격증 레벨이 Qb라면, A의 임금은 Qa * k, B의 임금은 Qb * k가 되어야 한다. 노동자들에게 지급하는 임금은 정수가 아닌 실수 범위여도 무방하다.
재현이는 수중에 W달러를 가지고 있으며, 사실 재현이는 자격증에 대해서는 별로 관심이 없고 그저 건물을 빨리 짓고 싶기 때문에, 자격증 레벨과 상관없이 현재 자금 내에서 가장 많은 노동자들을 고용하고 싶어 한다. 만약 고용할 수 있는 노동자의 수가 같다면, 노동자들에게 최소 비용을 지급하는 고용 방안을 원하며, 노동자의 수와 비용이 같다면 어떤 방법이든지 상관 없다. 재현이를 도와, 고용할 수 있는 노동자의 최대 수와 그 때 고용해야 할 노동자를 구하여라.
입력
표준 입력으로부터 다음의 데이터를 읽어야 한다:
- 첫째 줄에는 N과 W가 주어진다.
- 이후 N개 줄에 각 노동자의 정보가 주어진다. 이후 주어지는 정보의 i번째 줄에는 i번째 노동자의 최저임금 Si, 자격증 레벨 Qi가 주어진다.
출력
표준 출력에 최대로 고용할 수 있는 노동자의 수 H를 출력하며, 이후 H개의 줄에 고용하고 싶어하는 노동자들의 번호를 출력한다. 노동자들의 번호는 제각기 달라야 하며 순서는 어떤 순서여도 상관없다.
제한
- 1 ≤ N ≤ 500,000 지원 노동자의 수
- 1 ≤ Si ≤ 20,000 노동자 i의 최저임금
- 1 ≤ Qi ≤ 20,000 노동자 i의 자격증 레벨
- 1 ≤ W ≤ 10,000,000,000 사용할 수 있는 돈의 양
- 입력으로 주어지는 수는 모두 정수이다.
예제 입력 1
4 100 5 1000 10 100 8 10 20 1
예제 출력 1
2 2 3
예제 입력 2
3 4 1 2 1 3 1 3
예제 출력 2
3 1 2 3
예제 입력 3
3 40 10 1 10 2 10 3
예제 출력 3
2 2 3
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호