3120 : 기수정렬(Radix Sort)
- 제한시간
- 3000 ms
- 메모리제한
- 256 MB
- 해결횟수
- 23 회
- 시도횟수
- 202 회
문제
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개의 질의가 공백으로 구분하여 입력된다.
질의는 1-base로 주어진다.(즉 맨 앞의 원소는 0번째가 아닌 1번째이다.)
다음 행에 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!