Submission #329369

#	Time	Username	Problem	Language	Result	Execution time	Memory
329369		radaiosm7	Cave (IOI13_cave)	C++98	100 / 100	290 ms	768 KiB

cave

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

void exploreCave(int n) {
  int i, lo, hi, mid, j, rtr;
  int tr[n];
  int sw[n];
  int test[n];
  vector<int> avail;

  for (i=0; i < n; i++) {
      tr[i] = -1;
      avail.push_back(i);
  }

  for (i=0; i < n; i++) {
      for (j=0; j < n; j++) {
        test[j] = max(tr[j], 0);
      }

      if (tryCombination(test) == i) {
        rtr = 1;
      }

      else {
        rtr = 0;
      }

      lo = 0;
      hi = avail.size()-1;



      while (lo < hi) {
          mid = (lo+hi)/2;

          for (j=lo; j <= mid; j++) {
            test[avail[j]] = 1-rtr;
          }

        for (j=mid+1; j <= hi; j++) {
          test[avail[j]] = rtr;
        }

        if (tryCombination(test) == i) {
            hi = mid;
        }

        else {
          lo = mid+1;
        }
      }

      sw[avail[lo]] = i;
      tr[avail[lo]] = rtr;
      avail.erase(find(avail.begin(), avail.end(), avail[lo]));
  }

  answer(tr, sw);
}

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