This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "key.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;
}
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;
while(low != mid) {
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];
if(countIdx[i-1] != 0 ) {
TakeKey(now);
TakeKey(dir[now]);
}
if(Explore() == i) continue;
dir[now] = -1;
int find = 1;
// 지들끼리 문열어줌
for(int k = 0; k < countIdx[i]; k++) {
if(k == j) continue;
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) {
Report(i, room);
report[i][room] = 1;
room = dir[room];
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |