Submission #648883

#	Time	Username	Problem	Language	Result	Execution time	Memory
648883		Truitadepatates	Cave (IOI13_cave)	C++17	100 / 100	809 ms	468 KiB

cave

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

#include "cave.h"

void exploreCave(int n) {
  int S[n];
  int D[n];
  int Sol[n];
  bool fet[n];
  for (int i = 0; i < n; i++){
    S[i] = 0;
    D[i] = -1;
    Sol[i] = -1;
    fet[i] = false;
  }
  if (tryCombination(S) == -1){
    for (int i = 0; i < n; i++){
      S[i] = 1;
      D[i] = tryCombination(S);
      S[i] = 0;
    }
  }
  else{
    for (int i = 0; i < n; i++){
      int hola;
      if (tryCombination(S) == i) hola = 1;
      else hola = 0;
      int l = 0, r = n-1;
      while (l < r) {
        int m = (l+r)/2;
        for (int j = 0; j < n; j++) {
          if (fet[j]) Sol[j] = S[j];
          else Sol[j] = 0;
        }
        for (int j = l; j <= m; j++){
          if (not fet[j]){
            Sol[j] = 1;
          }
        } 
        if (hola == 1){
          if (tryCombination(Sol) == i) l = m+1;
          else r = m;
        }
        else{
          if (tryCombination(Sol) == i) r = m;
          else l = m+1;
        }
      }
      S[r] = hola;
      fet[r] = true;
      D[r] = i;
    }
  }
  answer(S, D);
}

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