Submission #997283

#	Time	Username	Problem	Language	Result	Execution time	Memory
997283		Marszpace	Cave (IOI13_cave)	C++14	100 / 100	217 ms	600 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 tryCombination(int *S);
void answer(int *S, int *D);
int nN;

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());
  if(res==-1){res=nN;}
  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) {
  nN=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());
    if(init==-1){init=N;}
    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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24