Submission #988453

#	Time	Username	Problem	Language	Result	Execution time	Memory
988453		kachim2	Cave (IOI13_cave)	C11	100 / 100	993 ms	752 KiB

cave

#include "cave.h"
#include <memory.h>
#include <stdio.h>
int already[5000] ;
void fillarr(int *arr, int l, int r) {
  for (int i = 0; i < 5000; i++) {
    if (already[i] == -1 && i >= l && i < r) {
      arr[i] = 1;
    } else if(already[i] == -1 || already[i] == 0) {
      arr[i]  = 0;
    }else {
      arr[i] = 1;
    }
  }
}
int binsearch(int n, int which) {
  int arr[5000];
  for (int i = 0; i < 5000; i++) {
    if (already[i] == -1 || already[i] == 0)
      arr[i] = 0;
    else
      arr[i] = 1;
  }
  int corr = 1;
  const int tmpcom = tryCombination(arr);
  if ( tmpcom> which ||tmpcom==-1){ 
    corr = 0;
  }
  int r = n;
  int l = 0;
  while ( r -l >1) {
    const int mid = (l + r) / 2;
    fillarr(arr, mid, r);
    const int res = tryCombination(arr);
    if ((res > which || res == -1) == corr) {
      l = mid;
    }else {
      r = mid;
    }
  }
  already[l] = corr;
  return l;
}
void exploreCave(int N) {
  for (int i = 0; i < 5000; i++)
    already[i] = -1;
  
  int D[5000];
  for (int i = 0; i < N; i++) {
    D[binsearch(N, i)] = i;
  }
  answer(already,D);
}

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