comkiwer- 기수정렬(Radix Sort) > 문제은행 : 정보올림피아드&알고리즘



3120 : 기수정렬(Radix Sort)

제한시간
3000 ms   
메모리제한
256 MB   
해결횟수
42 회   
시도횟수
282 회   

문제

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(intint*);
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!



출처

comkiwer

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP