Submission #252620

#	Time	Username	Problem	Language	Result	Execution time	Memory
252620		ChrisT	Cave (IOI13_cave)	C++17	100 / 100	349 ms	632 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int which[5001],N;
int up[5001], isUp[5001];
bool check (int s[], int cur) {
  int ret = tryCombination(s);
  return ret == -1 || ret > cur;
}
void exploreCave (int n) {
    memset(which,-1,sizeof which);
    for (int cur = 0; cur < n; cur++) {
      for (int x = 0; x < n; x++) {
        if (which[x] == -1) up[x] = 0;
        else up[x] = isUp[x];
      }
      bool curup = !check(up,cur);
      int low = 0, high = n-1;
      while (low < high) {
        int mid = (low+high)>>1;
        for (int x = low; x <= mid; x++) if (which[x] == -1) up[x] = curup;
        for (int x = mid+1; x <= high; x++) if(which[x] == -1) up[x] = !curup;
        if (check(up,cur)) high = mid;
        else low = mid+1;
      }
      which[low] = cur;
      isUp[low] = curup;
    }
    answer(isUp,which);
}

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