3120 : 기수정렬(Radix Sort)
- 제한시간
- 3000 ms
- 메모리제한
- 256 MB
- 해결횟수
- 15 회
- 시도횟수
- 91 회
문제
N개의 정수가 담긴 배열 A가 주어진다.
( 1<=N<=25,000,000), ( A ∋ a, -231 <= a < 231)
이 배열에 대하여 M개의 질의에 답하는 프로그램을 작성하시오.
( 1 <= M <= 10,000)
질의는 " A 배열을 오름차순 정렬했을때 idx번째 값은 얼마인가? " 이다.
( 1 <= idx <= N)
각 질의에 대하여는 실시간으로 답하여야 한다.
아래 main 코드는 사용자의 코드작성을 돕기 위한것으로
실제 채점시에는 다른 방법으로 채점할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | //=== user code template === /// 배열 A와 원소의 개수 N을 전달받아 초기화한다. void initUser(int nSize, int *arr){ } /// " A 배열을 오름차순 정렬했을때 idx번째 값은 얼마인가? " /// 라는 질의에 실시간으로 답하는 함수이다. int query(int idx){ } //=== main code template === #include <stdio.h> const int NMAX = (int)25e6; const int QMAX = 10000; static int N, A[NMAX + 1]; static int M, Q[QMAX + 1]; static int ans[QMAX + 1]; extern void initUser(int, int*); extern int query(int); static void input(){ scanf("%d", &N); for(int i=0;i<N;++i){ scanf("%d", A + i); } scanf("%d", &M); for(int i=0;i<M;++i){ scanf("%d", Q + i); } for(int i=0;i<M;++i){ scanf("%d", ans + i); } } static bool process(){ initUser(N, A); for(int i=0;i<M;++i){ int result = query(Q[i]); if(result != ans[i]) return 0; } return 1; } int main(){ //freopen("input.txt", "r", stdin); input(); if(process()) puts("100"); else puts("0"); return 0; } | cs |
입력형식
첫 행에 N이 공백으로 구분되어 주어진다. 다음 행에 A배열의 원소 N개가 공백으로 구분되어 입력된다.
다음 행에 질의의 개수 Q가 입력된다.
다음 행에 Q개의 질의가 공백으로 구분하여 입력된다.
다음 행에 Q개의 질의에 대한 답이 공백으로 구분하여 입력된다.
출력형식
이 문제는 상호작용문제(Interactive Problem)이다.
유저는 user code template 에 있는 내용만 작성하여 제출한다.
출력은 채점서버에 있는 main 함수에서 이루어진다.
입력 예8 7 15 3 0 9 10 1 11 5 2 3 8 1 7 1 3 15 0 11 |
출력 예100 |
Hint!