Submission #1109474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109474		SonicML	Cave (IOI13_cave)	C++14	100 / 100	356 ms	812 KiB

cave

#include <iostream>
#include "cave.h"

int n;

int const NMAX = 5000;
int query[1 + NMAX];
bool fixed[1 + NMAX];

int sol[2][1 + NMAX];

void printQuery() {
  for(int i = 0;i < n;i++) {
    std::cerr << query[i] << ' ';
  }
  std::cerr << '\n';
}
void buildQuery(int val1, int val2, int mid) {
  int ind = 0;
  for(int i = 0;i < n;i++) {
    if(!fixed[i]) {
      ind++; 
      if(ind <= mid) {
	query[i] = val1;
      }else {
	query[i] = val2;
      }
    }
  }
}

int getPos(int mid) {
  int ind = 0;
  for(int i = 0;i < n;i++) {
    if(!fixed[i]) {
      ind++;
      if(ind == mid) {
	return i;
      }
    }
  }
  return -1;
}

int cautbin(int from, int to, int val1, int val2, int target) {
  //std::cerr << from << ' ' << to << " :\n";
  if(from >= to) {
    return from;
  }else {
    int mid = (from + to) / 2;
    buildQuery(val1, val2, mid);
    int temp = tryCombination(query);
    //printQuery();
    //std::cerr << "  " << target << ' ' << mid << ' ' << temp << '\n';
    if(temp == -1 || temp > target) {
      return cautbin(from, mid, val1, val2, target);
    }else {
      return cautbin(mid+1, to, val1, val2, target);
    }
  }
}

void solve() {
  for(int i = 0;i < n;i++) {
    int temp, val1 = 1, val2 = 0;
    buildQuery(0, 0, 0);  
    //printQuery();
    temp = tryCombination(query); 
    //std::cerr << temp << '\n';
    if(temp == -1 || temp > i) {
      val1 = 0;
      val2 = 1; 
    }
    //std::cerr << i << ":\n";
    int pos = getPos(cautbin(1, n-i, val1, val2, i));
    //std::cerr << pos << "\n\n";
    query[pos] = val1;
    fixed[pos] = true;
    sol[0][pos] = val1;
    sol[1][pos] = i; 
  }
}

void exploreCave(int N) {
  n = N;
  solve(); 
  answer(sol[0], sol[1]);
}

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