기수정렬(Radix Sort) timer 3초 memory 512MB

[문제]

N개의 정수가 담긴 배열 A가 주어진다. ( 1≤N≤​25,000,000), ( A ∋ a,  -2^{31} ≤​ a < 2^{31})

이 배열에 대하여 M개의 질의에 답하는 프로그램을 작성하시오. ( 1 ≤​ M ≤​ 10,000)

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

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

아래 main 코드는 사용자의 코드작성을 돕기 위한것으로 실제 채점시에는 다른 방법으로 채점할 수 있다.

[CPP code template]

// main.cpp
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#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 
/// 배열 A와 원소의 개수 N을 전달받아 초기화한다.
void initUser(int nSize, int *arr) {

}

/// " A 배열을 오름차순 정렬했을때 idx번째 값은 얼마인가? "
/// 라는 질의에 실시간으로 답하는 함수이다.
int query(int idx) {

}