Submission #997282

#	Time	Username	Problem	Language	Result	Execution time	Memory
997282		Marszpace	Cave (IOI13_cave)	C++14	0 / 100	120 ms	348 KiB

cave

/*
 * With a little appreciation, in a mostly hollow tone, she says, "Delightful." As if the world has any meaning.
 * TASK : Cave
 * AUTHOR : Marszpace
*/

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

int swap(int k){
  if(k==1){return 0;}
  else{return 1;}
}

int find_button(vector<bool>& mask, vector<int>& states, int l, int r, int init, int n){
  if(l==r){return l;}

  // Find if it's in left or right
  int mid=(l+r)/2;
  for(int i=l;i<=mid;i++){
    if(!mask[i]){
      states[i]=swap(states[i]);
    }
  }
  int res=tryCombination(states.data());
  for(int i=l;i<=mid;i++){
    if(!mask[i]){
      states[i]=swap(states[i]);
    }
  }
  if((res==n)==(init==n)){
    return find_button(mask,states,mid+1,r,init,n);
  }
  else{
    return find_button(mask,states,l,mid,init,n);
  }
}

void exploreCave(int N) {
  vector<int> states(N,0);
  vector<bool> mask(N,false);
  vector<int> links(N,0);

  for(int i=0;i<N;i++){
    int init=tryCombination(states.data());
    int idx=find_button(mask,states,0,N-1,init,i);
    
    states[idx]=(init>i)?0:1;
    mask[idx]=true;
    links[idx]=i;
  }

  answer(states.data(),links.data());
}

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