Submission #329265

#	Time	Username	Problem	Language	Result	Execution time	Memory
329265		seedkin	Key of Impassable Doors (FXCUP3_key)	C11	100 / 100	23 ms	10220 KiB

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", maxCount);

	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;

			}		

		}



		// for(int j= 0; j< withCnt; j++) printf("%d ", with[j]);

		int head[1005];

		int headCnt = 0;

		for(int j = 0; j < withCnt; j++) {

			// printf("%d ", headCnt);

			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;

					} 

				}

				

				// printf("this");

				while(low != mid) {

					cnt = 0;

					TakeKey(now);

					for(int k = low; k < mid; k++) {

						TakeKey(head[k]);

						cnt += i;

					}

					int r = Explore();

					// printf("%d %d %d %d %d\n", now, cnt, r, low, high);

					if(r == cnt) {

						high = mid;

						mid = (low + high) / 2;

					} else {

						low = mid;

						mid = (low + high) / 2;

					}

				}

				// printf("this");				

				dir[now] = dir[head[low]];

				if(dir[now] == -1) dir[now] = head[low];

				dir[head[low]] = now;

				// printf("%d %d %d %d\n", now, dir[now], head[low], dir[head[low]]);

			}

		}

		// for(int j =0; j < headCnt; j++) printf("%d ", head[j]);

		// printf("\n");

	}



	



	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 / 23
• Subtask 2: 34 / 34
• Subtask 3: 43 / 43