#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++) {
int with[1005] = {0,};
int withCnt = 0;
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;
} else {
with[withCnt++] = now;
}
}
int head[1005];
int headCnt = 0;
for(int j = 0; j < withCnt; j++) {
int now = with[j];
if(headCnt == 0) head[headCnt++] = now;
else {
int low = 0;
int high = headCnt;
int mid = (low + high) / 2;
int cnt = 0;
{
TakeKey(now);
for(int k = low; k < high; k++) {
TakeKey(head[k]);
cnt += i;
}
int r = Explore();
if(r != cnt) {
head[headCnt++] = now;
continue;
}
}
while(low != mid) {
TakeKey(now);
for(int k = low; k < mid; k++) {
TakeKey(head[k]);
cnt += i;
}
int r = Explore();
if(r != cnt) {
high = mid;
mid = (low + high) / 2;
} else {
low = mid;
mid = (low + high) / 2;
}
}
dir[low] = dir[now];
if(dir[low] == -1) dir[low] = now;
dir[now] = low;
}
}
}
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 |
Runtime error |
1 ms |
1004 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
1004 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
1004 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
