Submission #681865

#	Time	Username	Problem	Language	Result	Execution time	Memory
681865		paulo_ar	Cave (IOI13_cave)	C++14	0 / 100	361 ms	388 KiB

cave

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

using namespace std;
 
int s [5000];
int res [5000];
bool activos [5000];
int ans [5000];
int busqueda (bool esuno, int inde, int n, int cont){
 
int izq=   1,  der=cont;
int mitad;
int rep=0;
  int index;
int master;
  int cf;
int indice;
if(esuno)master=0,cf=1;
else master=1,cf=0;
    while(izq<=der){
        mitad=(izq+der)/2;
        indice=1;
        int k=0;
      index=-9;
          while(k<n){
                if(activos[k]) {
                    s[k]=res[k];
                    
                }
                else if(indice<=mitad){
                    s[k]=master;
                    indice++;
                  
                }
                else{
                  if(index==-9)index=k;
                    s[k]=cf;
                }
                  
                k++;
           }
            
           int p = tryCombination(s);
         if(p>=inde or p==-1){
            der=mitad-1;
            rep=index;
         }
         else {
            izq=mitad+1;
         }
    }
    return rep;
}
 
 
void exploreCave(int N) {
 int des;
   int a;
   int cont;
   int ll;
    for(int i=0; i<N; i++){
        res[i]=0;
      activos[i]=false;
   }
 
   for(int j=1; j<=N; j++){
int master=1;
   for(int i=0; i<N; i++){
        if(activos[i]){
            s[i]=res[i];
        }
        else{
            s[i]=master;
        }
   }
  ll=tryCombination(s);
   
    cont = N-j+1;
   if(ll>=j or ll==-1){
       des= busqueda(true,j,N,cont);
       a=1;
   }
   else {
        des=busqueda(false,j,N,cont);
        a=0;
   }
 
   activos [des]=true;
   res[des]=a;
   ans[des]=j-1;
 
   }
 
    answer(res, ans);
 
 
  // int tryCombination(int S[]);
//void answer(int S[], int D[]);
//void exploreCave(int N);
}

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