Submission #49258

#	Time	Username	Problem	Language	Result	Execution time	Memory
49258		doowey	Cave (IOI13_cave)	C++14	100 / 100	1673 ms	580 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

const int MAXN = 5000;
int switch_[MAXN];
int on_off[MAXN];
int nn;

void fill(int until, int bit){
  for(int i = 0;i < nn;i ++ ){
    if(switch_[i] == -1){
      on_off[i] = (i < until ? bit : 1 - bit);
    }
  }
}

void open_door(int u){
  fill(nn, 1);
  int tt = tryCombination(on_off);
  int byt = 0;
  if(tt == -1 or tt > u)
    byt = 1;
  int lf = 0,rf = nn + 1;
  int md;
  while(rf-lf>1){
    md = (lf + rf) / 2;
    fill(md, byt);
    tt = tryCombination(on_off);
    if(tt == -1 or tt > u) 
      rf = md;
    else
      lf = md;
  }
  switch_[rf-1] = u;
  on_off[rf-1] = byt;
  fill(nn,0);
}

void exploreCave(int N) {
  for(int i = 0;i < MAXN;i ++ )
    switch_[i] = -1, on_off[i] = -1;
  nn = N;
  for(int i = 0;i < nn;i ++ )
    open_door(i);
  answer(on_off, switch_);
}

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