Submission #516447

#	Time	Username	Problem	Language	Result	Execution time	Memory
516447		600Mihnea	Cave (IOI13_cave)	C++17	51 / 100	233 ms	696 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5000 + 7;
int state[N];
int inv[N];
int guy[N];

void exploreCave(int n) {
  /**
  int S[] = {1, 1, 1, 0};
  int D[] = {3, 1, 0, 2};
  answer(S, D);
  **/
  vector<int> guys(n);
  iota(guys.begin(), guys.end(), 0);
  for (int pos = 0; pos < n; pos++) {
    int tl = 0, tr = (int) guys.size() - 1;
    while (tl < tr) {
      int tm = (tl + tr) / 2;
      vector<int> my_part;
      for (int j = tl; j <= tm; j++) {
        my_part.push_back(guys[j]);
      }
      int sol1 = tryCombination(state);
      if (sol1 == -1) sol1 = n;
      for (auto &x : my_part) state[x] ^= 1;
      int sol2 = tryCombination(state);
      if (sol2 == -1) sol2 = n;
      for (auto &x : my_part) state[x] ^= 1;

      bool ok1 = (sol1 >= pos + 1);
      bool ok2 = (sol2 >= pos + 1);

      if (ok1 == ok2) {
        tl = tm + 1;
      } else {
        tr = tm;
      }
    }
    int sol = tryCombination(state);
    if (sol == -1) sol = n;
    if (sol < pos + 1) {
      state[guys[tl]] ^= 1;
    }
    sol = tryCombination(state); /// this is pretty much just for assertion
    if (sol == -1) sol = n;
    assert(sol >= pos + 1);
    inv[guys[tl]] = pos;

    vector<int> pguys;
    for (int j = 0; j < (int) guys.size(); j++) {
      if (j != tl) {
        pguys.push_back(guys[j]);
      }
    }
    guys = pguys;
  }
  answer(state, inv);

}

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