기수정렬(Radix Sort)

기수정렬(Radix Sort)

 

제한시간: 3000 ms    메모리제한: 256 MB

 

N개의 정수가 담긴 배열 A가 주어진다.

( 1<=N<=25,000,000), ( A ∋ a,  -231 <= a < 231)

이 배열에 대하여 M개의 질의에 답하는 프로그램을 작성하시오.

( 1 <= M <= 10,000)

질의는 " A 배열을 오름차순 정렬했을때 idx번째 값은 얼마인가? " 이다.

( 1 <= idx <= N)

각 질의에 대하여는 실시간으로 답하여야 한다.

아래 main 코드는 사용자의 코드작성을 돕기 위한것으로

실제 채점시에는 다른 방법으로 채점할 수 있다.

 

//=== 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;
} 

 

첫 행에 N이 공백으로 구분되어 주어진다. 다음 행에 A배열의 원소 N개가 공백으로 구분되어 입력된다. 다음 행에 질의의 개수 Q가 입력된다. 다음 행에 Q개의 질의가 공백으로 구분하여 입력된다. 다음 행에 Q개의 질의에 대한 답이 공백으로 구분하여 입력된다.

 

8

7 15 3 0 9 10 1 11

5

2 3 8 1 7

1 3 15 0 11

 

100

 

//main.cpp
#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;
}

//user.cpp
#define KEY cnt[(a[i] >> k) & mask]

const int P = (1 << 8);
const int mask = P - 1;
int N, b[25000005], cnt[P], start, *a;

void r_sort(int *a, int *b)
{
	int i, j, k, *t;
	for (k = 0; k < 32; k += 8) {
		for (i = 0; i < P; i++) cnt[i] = 0;
		for (i = 0; i < N; i++) KEY++;
		for (i = 1; i < P; i++) cnt[i] += cnt[i - 1];
		for (i = N - 1; i >= 0; i--) b[--KEY] = a[i];
		t = a; a = b; b = t;
	}
}

void initUser(int nSize, int *arr) {
	N = nSize;
	a = arr;
	r_sort(arr, b);
	for (start = 0; start < N && a[start] >= 0; start++);
}

int query(int idx) {
	return a[(idx + start - 1) % N];
}