#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];
// printf("%d\n", now);
if(dir[now] != -1) continue;
// for(int k = 0; k< countIdx[i-1]; k++) {
// TakeKey(now);
// TakeKey(count[i-1][k]);
// int r = Explore();
// if(r == i) {
// dir[now] = count[i-1][k];
// break;
// }
// }
// if(dir[now] != -1) continue;
int low = 0;
int high = countIdx[i-1];
int mid = (low + high) / 2;
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];
// printf("%d\n", dir[now]);
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) {
// printf("%d %d\n", i, room);
Report(i, room);
report[i][room] = 1;
room = dir[room];
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
876 KB |
Output is correct |
| 4 |
Correct |
1 ms |
876 KB |
Output is correct |
| 5 |
Correct |
1 ms |
876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
876 KB |
Output is correct |
| 4 |
Correct |
1 ms |
876 KB |
Output is correct |
| 5 |
Correct |
1 ms |
876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 18 |
Correct |
3 ms |
3052 KB |
Output is correct |
| 19 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 20 |
Runtime error |
6 ms |
2924 KB |
Execution failed because the return code was nonzero |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
876 KB |
Output is correct |
| 4 |
Correct |
1 ms |
876 KB |
Output is correct |
| 5 |
Correct |
1 ms |
876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1152 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1388 KB |
Output is correct |
| 18 |
Correct |
3 ms |
3052 KB |
Output is correct |
| 19 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 20 |
Runtime error |
6 ms |
2924 KB |
Execution failed because the return code was nonzero |
| 21 |
Halted |
0 ms |
0 KB |
- |
