#include "key.h"
#include <stdio.h>
int dir[1005];
int count[1005][1005]; // [i][j]: i개 들어갈수있는 j번째 방
int countIdx[1005]; // i개 들어갈수있는 방의 갯수
int maxCount; // 가장 많이 들어갈수있는 방의 수
int report[1005][1005];
void EnsureKeyInfo(int N) {
for(int i = 0; i<= N; i++) {
dir[i] = -1;
countIdx[i] = 0;
for(int j =0; j<= N; j++) {
report[i][j] = 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;
}
// printf("%d\n", countIdx[2]);
for(int i = 2; i <= maxCount; i++) {
for(int j = 0; j < countIdx[i]; j++) {
int now = count[i][j];
if(dir[now] != -1) continue;
int low = 0;
int high = countIdx[i-1];
int mid = (low + high) / 2;
int flag = 0;
{
int visit[1005] = {0,};
int cnt = 0;
TakeKey(now);
for(int j = low; j < high; j++) {
int room = count[i-1][j];
TakeKey(room);
while(room != -1) {
if(visit[room] == 0) {
visit[room] = 1;
cnt++;
} else {
break;
}
room = dir[room];
}
}
int r = Explore();
if( r == cnt+1) {
flag = 1;
}
}
if(flag) {
while(low != mid) {
int visit[1005] = {0,};
int cnt = 0;
TakeKey(now);
for(int j = low; j < mid; j++) {
int room = count[i-1][j];
TakeKey(room);
while(room != -1) {
if(visit[room] == 0) {
visit[room] = 1;
cnt++;
} else {
break;
}
room = dir[room];
}
}
int r = Explore();
if( r == cnt+1) {
high = mid;
mid = (low + high) / 2;
} else {
low = mid;
mid = (low + high) / 2;
}
}
dir[now] = count[i-1][low];
continue;
}
int find = 1;
// 지들끼리 문열어줌
for(int k = j+1; k < countIdx[i]; k++) {
if(dir[count[i][k]] != -1) continue;
if(find == i) break;
TakeKey(now);
TakeKey(count[i][k]);
int r = Explore();
if(r == i) {
dir[now] = count[i][k];
now = dir[now];
find++;
}
}
dir[now] = count[i][j];
}
}
for(int i = 1; i <= N; i++) {
int room = i;
while(room != -1 && report[i][room] == 0) {
// printf("%d %d\n", i, room);
Report(i, room);
report[i][room] = 1;
room = dir[room];
}
}
}
