Submission #296848

#	Time	Username	Problem	Language	Result	Execution time	Memory
296848		Haunted_Cpp	Cave (IOI13_cave)	C++17	100 / 100	987 ms	888 KiB

cave

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

const int MAX_N = 5000 + 5;
int conn[MAX_N], optimal[MAX_N];
int estado[MAX_N], as[MAX_N];

void exploreCave(int n) {


  auto ask = [&](const vector<int> &arr) {
    for (int i = 0; i < n; i++) {
      as[i] = arr[i];
    }
    int res = tryCombination(as);
    return (res == -1 ? n : res);
  };


  vector<int> sw_state(n, -1);
  vector<int> sw_conn(n, -1);

  vector<int> state(n, 0);
  int current_door = ask(state);


  vector<int> valid_switch(n);
  iota(valid_switch.begin(), valid_switch.end(), 0);

  for (int porta_atual = 0; porta_atual < n; porta_atual++) {

    int lo = 0;
    int hi = (int) valid_switch.size();


    while(lo < hi) {
      const int mid = lo + (hi - lo) / 2 + 1;

      vector<int> arr(n);
      for (int i = 0; i < n; i++) {
        arr[i] = estado[i];
      }

      for (int i = 0; i < mid; i++) {
        const int s_i = valid_switch[i];
        arr[s_i] = 1;

      }

      int nxt_door = ask(arr);



      if (current_door > porta_atual) {
        if (nxt_door == porta_atual) {
          hi = mid - 1;
        } else {
          lo = mid;
        }
      } else {

        if (nxt_door > porta_atual) {
          hi = mid - 1;
        } else {
          lo = mid;
        }
      }
    }


    sw_conn[porta_atual] = valid_switch[hi];
    sw_state[porta_atual] = (current_door > porta_atual ? 0 : 1);

    valid_switch.erase(find(valid_switch.begin(), valid_switch.end(), valid_switch[hi]));
    estado[sw_conn[porta_atual]] = sw_state[porta_atual];

    int res = tryCombination(estado);
    current_door = (res == -1 ? n : res);

   // cout << "BOTAO DA PORTA: " << porta_atual << ' ' << sw_conn[porta_atual] << ' ' << sw_state[porta_atual] << '\n';
    conn[sw_conn[porta_atual]] = porta_atual;
    optimal[sw_conn[porta_atual]] = sw_state[porta_atual];


  }



  answer(optimal, conn);

}

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