제출 #366063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366063		KoD	동굴 (IOI13_cave)	C++17	100 / 100	679 ms	1004 KiB

cave

#include "cave.h"
#include <set>
#include <vector>

int S[5000];
int D[5000];

template <class T>
using Vec = std::vector<T>;

void exploreCave(int N) {
  const auto query = [&] {
    const auto ret = tryCombination(S);
    return ret == -1 ? N : ret;
  };
  std::set<int> remain;
  for (int i = 0; i < N; ++i) {
    remain.insert(i);
  }
  for (int d = 0; d < N; ++d) {
    // Which switch is connected to the door 'd' ?
    for (const auto x: remain) {
      S[x] = 0;
    }
    const auto allZero = query();
    Vec<int> cur(remain.begin(), remain.end());
    while (cur.size() > 1) {
      Vec<int> next;
      next.reserve((cur.size() + 1) / 2);
      while (cur.size() > next.size()) {
        next.push_back(cur.back());
        cur.pop_back();
      }
      for (const auto x: cur) {
        S[x] = 1;
      }
      const auto tmp = query();
      for (const auto x: cur) {
        S[x] = 0;
      }
      if ((allZero == d) == (tmp == d)) {
        cur = std::move(next);
      }
    }
    const auto i = cur.front();
    remain.erase(i);
    D[i] = d;
    S[i] = (allZero == d ? 1 : 0);
  }
  answer(S, D);
}

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