시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 692 | 37 | 24 | 21.239% |
CSHS(Computer Science High School)의 실습실에는 총 M대의 컴퓨터가 일렬로 놓여있다. 이 컴퓨터는 왼쪽에 있는 것부터 순서대로 1~M의 번호가 매겨져 있다.
현재, 이 실습실에는 총 N명의 학생들이 이미 앉아있으며, 각각 A1, A2, ..., AN번 컴퓨터 앞에 앉아있다. 곧 있으면 자습시간이 시작되기 때문에 총 M-N명의 학생이 더 와서 컴퓨터를 사용할 것이다.
각 학생들은 다른 학생이 자기 컴퓨터의 모니터를 보는 것을 싫어하므로 다음과 같은 방법으로 자리를 잡을 것이다.
진환이는 Q명의 친구들과 함께 팀 프로젝트를 해야 하기 때문에 Q명의 친구들이 어디에 앉을 지 알아야 한다. 다행히 진환이는 각 친구가 몇 번째로 실습실에 들어갔는지 알고 있다. 진환이를 도와 각 친구들의 위치를 구하.
첫 번째 줄에는 컴퓨터의 수 M, 이미 자리를 잡은 학생의 수 N, 친구의 수 Q가 주어진다.
두 번째 줄에는 N개의 정수가 주어지는데, 이 값은 자리를 잡은 학생의 위치 Ai를 나타낸다. 이미 자리를 잡은 학생들은 앞서 말한 방법으로 자리를 잡지 않았을 수도 있음에 유의하여라.
세 번째 줄에는 Q개의 정수가 주어지는데, 이 값은 각 친구가 실습실에 들어간 순서 Bi를 의미한다.
A와 B는 오름차순이다. 즉, 항상 1 ≤ A1 < A2 < . . . < AN ≤ M 와 1 ≤ B1 < B2 < . . . < BQ ≤ M를 만족한다.
출력은 총 Q개의 줄로 이루어진다. i번째 줄에는 i번째 친구가 자리잡은 컴퓨터의 번호를 출력한다. 처리하는 정수의 범위가 32비트 정수를 넘어가므로 64비트 정수형 변수를 사용하도록 한다.
모든 서브태스크에서 1 ≤ Q ≤ 105, N ≤ M 그리고 1 ≤ N ≤ 105를 만족한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 19 | 1 ≤ M ≤ 300 000 |
2 | 22 | 1 ≤ M ≤ 1014, BQ ≤ 300 000 |
3 | 59 | 1 ≤ M ≤ 1014 |
7 1 4 4 2 3 4 5
2 6 1 3
10 2 4 2 8 1 3 5 8
2 5 6 4
예제 2 설명
처음에는 2번 컴퓨터와 8번 컴퓨터에 학생이 있다.
추가적으로 오는 8명의 학생들은 순서대로 5, 3, 6, 9, 1, 4, 7, 10번 컴퓨터에 앉을 것이다.
Olympiad > Croatian Highschool Competitions in Informatics > 2015 > Croatian Olympiad in Informatics 2015 3번