oj.uz

Submission #328781

# Submission time Handle Problem Language Result Execution time Memory
328781 2020-11-18T04:49:35 Z seedkin Key of Impassable Doors (FXCUP3_key) C
0 / 100
 1 ms 620 KB 
#include "key.h"



int dir[1005];

int count[1005][1005]; // [i][j]: i개 들어갈수있는 j번째 방

int countIdx[1005]; // i개 들어갈수있는 방의 갯수

int maxCount; // 가장 많이 들어갈수있는 방의 수



void EnsureKeyInfo(int N) {

	for(int i = 0; i<= N; i++) {

		dir[i] = -1;

		countIdx[i] = 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];

			int low = 0;

			int high = countIdx[i-1];

			int mid = (low + high) / 2;

			while(low != high) {

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

		}

	}



	for(int i = 1; i <= N; i++) {

		int room = i;

		while(room != -1) {

			Report(i, room);

			room = dir[room];

		}

	}

}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Runtime error 1 ms 620 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Runtime error 1 ms 620 KB Execution failed because the return code was nonzero
3 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 Runtime error 1 ms 620 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -