Submission #410819

#	Time	Username	Problem	Language	Result	Execution time	Memory
410819		meperdonas203	Cave (IOI13_cave)	C++17	100 / 100	1046 ms	536 KiB

cave

#include<iostream>
#include "cave.h"
using namespace std;
bool fijo[70005];
int arre[70005];
int ans[70005];
int posiciones[70005];
bool uno(int pos,int N){
  for(int i=0;i<N;i++){
    if(!fijo[i]){
      arre[i]=1;
    }else{
      arre[i]=ans[i];
    }
  }
  return(tryCombination(arre)==pos);
}
bool cerrada(int medio, int pos,bool valor,int N){
  for(int i=0;i<=medio;i++){
    if(!fijo[i]){
      arre[i]=valor;
    }else{
      arre[i]=ans[i];
    }
  }
  for(int i=medio+1;i<N;i++){
    if(!fijo[i]){
      arre[i]=!valor;
    }else{
      arre[i]=ans[i];
    }
  }
  return(tryCombination(arre)==pos);
}
void bs(int indice,bool valor,int N){
  int ini=0,res=0,fin=N-1,medio;
  while(ini<=fin){
    medio=(ini+fin)/2;
    if(cerrada(medio,indice,valor,N)){
      res=medio;
      fin=medio-1;
    }else{
      ini=medio+1;
    }
  }
  fijo[res]=true;
  ans[res]=!valor;
  posiciones[res]=indice;
}
void exploreCave(int N) {
    for(int i=0;i<N;i++){
      bs(i,uno(i,N),N);
    }
    answer(ans,posiciones);
}

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