Submission #516457

#	Time	Username	Problem	Language	Result	Execution time	Memory
516457		600Mihnea	Cave (IOI13_cave)	C++17	100 / 100	246 ms	616 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);
  int last_guy = tryCombination(state);
  if (last_guy == -1) last_guy = n;

  iota(guys.begin(), guys.end(), 0);
  for (int pos = 0; pos < n; pos++) {
    int tl = 0, tr = (int) guys.size() - 1;
    int last = tr - tl + 1, per = 0;
    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 = last_guy;
      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;
      }
      assert(tr - tl + 1 < last);
    }
    ///cout << pos << " : " << per << "\n";
    int sol = tryCombination(state);
    if (sol == -1) sol = n;
    if (sol < pos + 1) {
      state[guys[tl]] ^= 1;
      last_guy = tryCombination(state);
      if (last_guy == -1) last_guy = n;
    }
    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);

}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:24:29: warning: unused variable 'per' [-Wunused-variable]
   24 |     int last = tr - tl + 1, per = 0;
      |                             ^~~

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