Submission #328847

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
328847	2020-11-18T08:15:50 Z	seedkin	Key of Impassable Doors (FXCUP3_key)	C	23 / 100	6 ms	3052 KB

key

#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;

				}

			}

			// 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 + (i-1) * (mid-low) ) {

			// 		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;

			if(dir[now] != -1) continue;

			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];

		}

	}

}

Subtask #1

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	1004 KB	Output is correct
3	Correct	1 ms	896 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	1280 KB	Output is correct
9	Correct	1 ms	1132 KB	Output is correct
10	Correct	1 ms	1132 KB	Output is correct
11	Correct	1 ms	1132 KB	Output is correct
12	Correct	1 ms	1152 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	1152 KB	Output is correct
17	Correct	1 ms	1388 KB	Output is correct

Subtask #2

0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	1004 KB	Output is correct
3	Correct	1 ms	896 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	1280 KB	Output is correct
9	Correct	1 ms	1132 KB	Output is correct
10	Correct	1 ms	1132 KB	Output is correct
11	Correct	1 ms	1132 KB	Output is correct
12	Correct	1 ms	1152 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	1152 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	2944 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	-

Subtask #3

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	1004 KB	Output is correct
3	Correct	1 ms	896 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	1280 KB	Output is correct
9	Correct	1 ms	1132 KB	Output is correct
10	Correct	1 ms	1132 KB	Output is correct
11	Correct	1 ms	1132 KB	Output is correct
12	Correct	1 ms	1152 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	1152 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	2944 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	-