Submission #492479

#	Time	Username	Problem	Language	Result	Execution time	Memory
492479		1ne	동굴 (IOI13_cave)	C++14	0 / 100	206 ms	588 KiB

cave

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

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