Submission #650813

#	Time	Username	Problem	Language	Result	Execution time	Memory
650813		Litusiano	Cave (IOI13_cave)	C++14	51 / 100	377 ms	460 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
 
#define MAX_N 5000
int v[MAX_N];
bool used[MAX_N];
 
void convert(int idx, int val){
  for(int i = 0; i<= idx; i++){
    if(used[i]) continue;
    v[i] = val;
  }
}
 
void exploreCave(int N) {
  /* ... */
  //int v[N];
  for(int i = 0; i<N; i++){
    v[i] = 0;
  }
  int s[N];
  // Busco combinacio correcte
  for(int i = 0; i<N-1; i++){
    bool ok = 0;
    int l = -1; int r = N-1;
    int val = 0; 
    convert(N-1,0);
    if(i == 2){
      /*cout<<"V ";
      for(int i = 0; i<N; i++) cout<<v[i]<<" ";
      cout<<endl;*/
    }
    if(tryCombination(v) == i) val = 1;
    convert(N-1,val^1);
    while(r > l+1){
      int m = (l+r)/2;
      convert(m,val);
      
      // si s'ha obert,
      int x = tryCombination(v);
      if (x == -1){
        ok = 1; break;
      }
      if(x == i){
        //tancat
        l = m;
      }
      else r = m;
      convert(m,val^1);
    }
    if(ok) break;
    //cout<<i<<" "<<l<<" "<<r<<" "<<val<<endl;
    used[r] = 1;
    v[r] = val;
  }
  int idx = 0;
  for(int i = 0; i<N;i++){
    if(!used[i]) idx = i;
  }
  v[idx] = 0;
  if(tryCombination(v) != -1) v[idx] = 1;
  for(int i = 0; i<N; i++){
      v[i] ^= 1;
      s[i] = tryCombination(v);
      v[i] ^= 1;
  }
  answer(v,s);
  //for(int i = 0; i<N; i++) cout<<v[i]<<" "; cout<<endl;
  //for(int i = 0; i<N; i++) cout<<s[i]<<" "; cout<<endl;
  return;
}

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