시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1448 | 590 | 478 | 41.820% |
백준 온라인 저지를 여행하다 보면 하나의 수열이 주어지고 여기에 여러 가지 연산을 하는 문제들을 만나볼 수 있습니다.
진수는 백준 온라인 저지에서 문제를 풀다 다음과 같은 문제를 찾았습니다.
길이가 N인 정수 수열 [a1, a2, ..., aN] 이 주어진다. 다음과 같은 연산들을 수행한 후 수열을 출력하는 프로그램을 작성하시오.
1 i x
: ai에 정수 x만큼 더한다.2 s
: 수열을 오른쪽으로 s칸 시프트한다.3 s
: 수열을 왼쪽으로 s칸 시프트한다.수열을 오른쪽으로 한 칸 시프트하면 수열 [a1, a2, …, aN-1, aN] 은 [aN, a1, a2, …, aN-1] 이 되고
수열을 왼쪽으로 한 칸 시프트하면 수열 [a1, a2, …, aN-1, aN] 은 [a2, …, aN-1, aN, a1] 이 된다.
진수는 빠르게 코딩하여 제출하였는데 '시간 초과' 판정을 받았습니다.
진수가 작성한 코드는 시프트 연산을 수행할 때마다 반복문이 N번 실행되어 너무 느리기 때문입니다.
진수는 이 문제를 풀어 '맞았습니다!!' 를 띄워줄 누군가를 기다리고 있습니다.
첫 번째 줄에 수열의 길이 N (2 ≤ N ≤ 200,000) 과 연산의 개수 Q (1 ≤ Q ≤ 200,000) 가 주어집니다.
두 번째 줄에는 정수 a1, a2, ..., aN (-10,000 ≤ ai ≤ 10,000) 이 주어집니다.
다음 Q개의 줄에는 각 줄 마다 연산이 주어집니다.
첫 번째 줄에 Q개의 연산을 차례대로 수행한 후 a1, a2, …, aN 을 공백을 사이에 두고 출력합니다.
5 4 1 2 3 4 5 1 1 4 2 3 1 2 2 3 1
6 5 5 2 3
[1, 2, 3, 4, 5]
(1, 1, 4) : a_1 에 4를 더합니다.
[5, 2, 3, 4, 5]
(2, 3) : 오른쪽으로 3칸 시프트 합니다.
[3, 4, 5, 5, 2]
(1, 2, 2) : a_2 에 2를 더합니다.
[3, 6, 5, 5, 2]
(3, 1) : 왼쪽으로 1칸 시프트 합니다.
[6, 5, 5, 2, 3]
University > 경북대학교 > 2019 Goricon D번