Submission #157968

#	Time	Username	Problem	Language	Result	Execution time	Memory
157968		WLZ	Cave (IOI13_cave)	C++14	100 / 100	453 ms	680 KiB

cave

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

void exploreCave(int N) {
  vector<int> done(N, 0);
  int S[N], D[N];
  for (int i = 0; i < N; i++) {
    S[i] = 0;
  }
  for (int i = 0; i < N; i++) {
    vector<int> v;
    for (int j = 0; j < N; j++) {
      if (!done[j]) {
        v.push_back(j);
      }
    }
    int cur[N];
    copy(S, S + N, cur);
    int op = (tryCombination(cur) == i);
    int l = 0, r = (int) v.size() - 1;
    while (l < r) {
      int m = (l + r) / 2;
      copy(S, S + N, cur);
      for (int j = l; j <= m; j++) {
        cur[v[j]] = op;
      }
      for (int j = m + 1; j <= r; j++) {
        cur[v[j]] = !op;
      }
      if (tryCombination(cur) == i) {
        l = m + 1;
      } else {
        r = m;
      }
    }
    S[v[l]] = op;
    D[v[l]] = i;
    done[v[l]] = 1;
  }
  answer(S, D);
}

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