제출 #29928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29928		kavun	동굴 (IOI13_cave)	C++14	0 / 100	335 ms	512 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[lo] = true;
      correct[lo] = flag;
      d[lo] = leftmost;
      return make_pair(lo,leftmost);
    }
  int pos = process(lo,hi);
  if(pos == -1)
    pos = n;

  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++)
    {
      leftmost = tryCombination(s);
      if(leftmost == -1)
	leftmost = n;

      pair<int,int> pr = search(0,n-1,0);
      s[pr.first] = correct[pr.first];
    }

  answer(s,d);
}

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