#include "key.h"
int dir[1005];
int count[1005][1005]; // [i][j]: i개 들어갈수있는 j번째 방
int countIdx[1005]; // i개 들어갈수있는 방의 갯수
int maxCount; // 가장 많이 들어갈수있는 방의 수
void EnsureKeyInfo(int N) {
for(int i = 0; i<= N; i++) {
dir[i] = -1;
countIdx[i] = 0;
}
maxCount = 0;
for(int i = 1; i <= N; i++) {
TakeKey(i);
int cnt = Explore();
count[cnt][countIdx[cnt]] = i;
countIdx[cnt]++;
if(cnt > maxCount) maxCount = cnt;
}
for(int i = 2; i <= maxCount; i++) {
for(int j = 0; j < countIdx[i]; j++) {
int now = count[i][j];
int low = 0;
int high = countIdx[i-1];
int mid = (low + high) / 2;
while(low != high) {
TakeKey(now);
for(int j = low; j< mid; j++) {
TakeKey(count[i-1][j]);
}
int r = Explore();
if( r == i ) {
high = mid;
mid = (low + high) / 2;
} else {
low = mid;
mid = (low + high) / 2;
}
}
dir[now] = count[i-1][low];
}
}
for(int i = 1; i <= N; i++) {
int room = i;
while(room != -1) {
Report(i, room);
room = dir[room];
}
}
}
