Submission #492493

#	Time	Username	Problem	Language	Result	Execution time	Memory
492493		1ne	동굴 (IOI13_cave)	C++14	100 / 100	966 ms	708 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
 
void exploreCave(int n) {
    /* ... */
    int cur = 0;
    int swit[n];
  	int ans[n];
  	for (int i = 0;i<n;++i)swit[i] = -1;
    while(cur<n){
    	function<int(int,int,int)> solve = [&](int val,int left ,int right){
    	if (right - left<1)return left;
  	  int mid = (left + right)>>1;
  	  int temp[n];
  	  for (int i = 0;i<left;++i){
  	  	if (swit[i]==-1){
  	  		temp[i] = val^1;
  	  	}
  	  	else temp[i] = ans[i];
  	  }
  	  for (int i  = left;i<=mid;++i){
  	     if (swit[i]==-1){
  	     	temp[i] = val;
  	     }
  	     else{
  	       temp[i] = ans[i];
  	     }
  	  }
  	  for (int i = mid+1;i<n;++i){
  	  	if (swit[i]==-1){
  	  		temp[i] = val^1;
  	  	}
  	  	else{
  	  	   temp[i] = ans[i];
  	  	}
  	  }
  	  int anss;
  	  int a = tryCombination(temp);
  	  if (a>cur || a==-1){
  	   	 anss = solve(val,left,mid); 
  	  }
  	  else anss = solve(val,mid+1,right);
  	  return anss;
  	};
    	int val = -1;
      	for (int j = 0;j<1;++j){
        	int temp[n] = {0};
        	for (int i = 0;i<n;++i){
        		if (swit[i]==-1){
        			temp[i] = j;
        		}
        		else temp[i] = ans[i];
        	}
        	int a = tryCombination(temp);
        	if (a>cur||a==-1){
        		val = j;
        		break;
        	}
       }
      if (val==-1)val=1;
      int left = solve(val,0,n-1);
//      cout<<left<<" "<<val<<" "<<cur<<'\n';
      swit[left] = cur;
      ans[left] = val;
      //cout<<left<<" "<<cur<<'\n';
      ++cur;
    }
    answer(ans,swit);
 }

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