Submission #468952

#	Time	Username	Problem	Language	Result	Execution time	Memory
468952		Soumya1	Cave (IOI13_cave)	C++14	100 / 100	862 ms	460 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
  int pos[n], state[n];
  int s[n] = {0};
  // int cur = tryCombination(s);
  // if (cur == 0) {
  //   for (int i = 0; i < n; i++) {
  //     s[i] = 1;
  //     if (tryCombination(s) > 0) {
  //       pos[0] = i;
  //       state[i] = 1;
  //       break;
  //     }
  //     s[i] = 0;
  //   }
  // } else {
  //   for (int i = 0; i < n; i++) {
  //     s[i] = 1;
  //     if (tryCombination(s) == 0) {
  //       pos[0] = i;
  //       state[i] = 0;
  //       break;
  //     }
  //     s[i] = 0;
  //   }
  // }
  for (int i = 0; i < n; i++) {
    int cur = tryCombination(s);
    int l = 0, r = n - 1;
    if (cur == i) {
      while (l < r) {
        int m = (l + r) >> 1;
        int ss[n];
        for (int j = 0; j < n; j++) ss[j] = s[j];
        for (int j = 0; j <= m; j++) ss[j] ^= 1;
        for (int j = 0; j < i; j++) ss[pos[j]] = state[j];
        if (tryCombination(ss) != i) {
          r = m;
        } else {
          l = m + 1;
        }
      }
      pos[i] = l;
      state[i] = s[l] ^ 1;
      s[l] ^= 1;
    } else {
      while (l < r) {
        int m = (l + r) >> 1;
        int ss[n];
        for (int j = 0; j < n; j++) ss[j] = s[j];
        for (int j = 0; j <= m; j++) ss[j] ^= 1;
        for (int j = 0; j < i; j++) ss[pos[j]] = state[j];
        if (tryCombination(ss) == i) {
          r = m;
        } else {
          l = m + 1;
        }
      }
      pos[i] = l;
      state[i] = s[l];
    }
  }
  int d[n];
  for (int i = 0; i < n; i++) {
    d[pos[i]] = i;
    s[pos[i]] = state[i];
  }
  answer(s, d);
}

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