Problem E : 기수정렬(Radix Sort)

N개의 정수가 담긴 배열 A(1<=N<=25,000,000)

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

(1<=M<=10,000)

 

#include <stdio.h>

const int NMAX = (int)25e6; // N개의 정수가 주어짐
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); // A배열에 숫자를 입력 받음
	}

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

#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++; // 32비트를 4분할 해서 처음 4비트부터 마지막 4비트 까지 순서를 정렬함
		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; // 그래서 정렬된 b를 다시 a로 넣음
	}
}

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];
}

8 7 15 3 0 9 10 1 11 5 2 3 8 1 7 1 3 15 0 11

100