Submission #1264746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264746		comgaTramAnh	Cave (IOI13_cave)	C++20	100 / 100	211 ms	548 KiB

cave

#include <vector>
#include "cave.h"
void exploreCave(int N) {
  std::vector <int> finalSwitch(N), finalS(N);
  int S[N], D[N];
  std::vector <bool> found(N);
  for (int i = 0; i < N; i++) {
    S[i] = 0; 
    D[i] = i; 
    found[i] = false; 
  }             
  for (int i = 0; i < N; i++) {
    int tmp[N];
    for (int j = 0; j < N; j++) {
      tmp[j] = S[j]; 
    } 
    int door = tryCombination(tmp);
    finalS[i] = 1; 
    if (door != i) {
      finalS[i] = 0; 
      for (int j = 0; j < N; j++) {
        if (found[j] == false) {
          tmp[j] = 1 - tmp[j];  
        }
      }
    }
    int lo = 0, hi = N - 1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2; 
      for (int j = lo; j <= mid; j++) {
        if (found[j] == false) {
          tmp[j] = 1 - tmp[j];   
        }
      }
      door = tryCombination(tmp); 
      if (door != i) {
        finalSwitch[i] = mid; 
        hi = mid - 1; 
        for (int j = lo; j <= mid; j++) {
          if (found[j] == false) {
            tmp[j] = 1 - tmp[j]; 
          }
        }
      }
      else {
        lo = mid + 1;   
      }
    }
    found[finalSwitch[i]] = true;
    S[finalSwitch[i]] = finalS[i];
    D[finalSwitch[i]] = i;       
  }
  answer(S, D); 
}

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