Submission #729495

#	Time	Username	Problem	Language	Result	Execution time	Memory
729495		NeroZein	Cave (IOI13_cave)	C++17	13 / 100	244 ms	376 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std; 
 
const int N = 5005;
 
bool vis[N];
 
void exploreCave(int N_) {
  int n;
  n = N_;
  int a[n]; 
  for (int i = 0; i < n; ++i) {
    a[i] = 0; 
  }
  for (int i = 0; i < n; ++i) {
    int l = 0, r = n; 
    while (l < r) {
      int mid = (l + r) >> 1; 
      for (int j = 0; j <= mid; ++j) {
        if (!vis[j]) {
          a[j] = 0; 
        }
      }
      int z = tryCombination(a);
      if (z == -1 || z > i) {
        r = mid;
      } else {
        l = mid + 1; 
      }
    }
    //cout << l << ' '; 
    if (l != n) {
      a[l] = 0;
      vis[l] = true; 
    } else {
      l = 0, r = n - 1; 
       while (l < r) {
        int mid = (l + r) >> 1; 
        for (int j = 0; j <= mid; ++j) {
          if (!vis[j]) {
            a[j] = 1; 
          }
        }
        int z = tryCombination(a);
        if (z == -1 || z > i) {
          r = mid;
        } else {
          l = mid + 1; 
        }
      }
      vis[l] = true;
      a[l] = 1; 
      //cout << l << ' ';
    }
    //cout << '\n'; 
  } 
  int d[n];
  for (int i = 0; i < n; ++i) {
    d[i] = 0; 
  }
  for (int i = 0; i < n; ++i) {
    a[i] ^= 1; 
    int x = tryCombination(a); 
    d[i] = x; 
    a[i] ^= 1; 
  }
  answer(a, d);
}

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