제출 #1131584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131584		altern23	동굴 (IOI13_cave)	C++20	100 / 100	357 ms	572 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

int ans[5005], halleluya[5005], v[5005], jawab[5005], vis[5005];
void exploreCave(int N){	
    for(int i = 0; i < N; i++){
    	for(int j = 0; j < N; j++){
			if(vis[j]) v[j] = halleluya[j];
			else v[j] = 1;
		}

    	int id = (tryCombination(v) == i);
		int lf = 0, rg = N - 1, now = -1;
		for(;lf <= rg;){
			int mid = (lf + rg) / 2;
			for(int j = 0; j < N; j++){
				if(vis[j]){
					jawab[j] = halleluya[j];
					continue;
				}
				if(j <= mid){
					jawab[j] = id;
				}
				else{
					jawab[j] = (id ^ 1);
				}
			}
			if(tryCombination(jawab) == i){ 
				now = mid;
				rg = mid - 1;
			}
			else lf = mid + 1;
		}
		
		ans[now] = i;
		halleluya[now] = id ^ 1;
		vis[now] = 1;
	}
	
	answer(halleluya, ans);
}

/*
switch
0 0 0 0 0 0 --> 3
1 1 1 1 1 1 --> 0

1 1 1 0 0 0 --


pintu 0 --> 4 (udah tau)
pintu 1 --> 2

switch: 0 1 2 3 5 6 7 8 9
ng
*/

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24