제출 #339930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339930		Kerim	동굴 (IOI13_cave)	C++17	100 / 100	1117 ms	640 KiB

cave

#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
void exploreCave(int n) {
	vector<int>a(n),b(n),c(n);
	for(int i=0;i<n;i++)a[i]=-1;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(~a[j])c[j]=a[j];
			else c[j]=0;
		}
		int val=(tryCombination(c.data())==i);
		int st=0,en=n-1;
		while(st<en){
			int mid=(st+en+1)>>1;
			for(int j=0;j<n;j++){
				if(~a[j])c[j]=a[j];
				else c[j]=val^(j<mid);	
			}
			if(tryCombination(c.data())==i) en=mid-1;
			else st=mid;
		}
		for(int j=0;j<n;j++){
			if(~a[j])c[j]=a[j];
			else c[j]=val^(j<en);	
		}a[st]=val,b[st]=i;
	}
	answer(a.data(),b.data());
}

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