Submission #29854

#	Time	Username	Problem	Language	Result	Execution time	Memory
29854		kavun	Cave (IOI13_cave)	C++14	0 / 100	261 ms	516 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;
int n, correct[5010], d[5010], done, leftmost, s[5010];
bool mk[5010];

int process(int lo, int hi)
{
  int m = (lo + hi) / 2;
  for(int i = 0; i < n; i++)
    if(!mk[i])
      s[i] = 0;

  for(int i = lo; i <= m; i++)
    if(!mk[i])
      s[i] = 1;

  return tryCombination(s);
}

pair<int,int> search(int lo, int hi, int flag)
{
  int m = (lo + hi) / 2;
  if(lo == hi)
    {
      mk[leftmost] = true;
      correct[lo] = flag;
      d[lo] = leftmost;
      return make_pair(lo,leftmost);
    }
  int pos = process(lo,hi);

  if(pos > leftmost)
    return search(lo,m,1);
  else if(pos == leftmost)
    return search(m+1,hi,1);
  else
    {
      leftmost = pos;
      return search(lo,m,0);
    }
}

void exploreCave(int N) {
  n = N;
  for(int i = 0; i < n; i++)
    {
      pair<int,int> pr = search(0,n-1,0);
      s[pr.first] = pr.second;
    }

  answer(s,d);
}

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