Submission #166686

#	Time	Username	Problem	Language	Result	Execution time	Memory
166686		NaimSS	Cave (IOI13_cave)	C++14	100 / 100	442 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
int S[5050];
int s[5050];
int con[5050];

void exploreCave(int N) {
    /* ... */
    int n = N;
    
    for(int i=0;i<n;i++)S[i]=-1;
    
    for(int k=0;k<N;k++){
        
        for(int i=0;i<n;i++){
            if(S[i]!=-1)s[i] = S[i];
            else s[i]=0;
        }
        
        int x = tryCombination(s);
        
        if(x>k || x==-1){
            //o certo para ele é 0;
            
            int l = 0, r = n-1;
            int pos = -1;
            while(l<=r){
               int m = (l+r)>>1;
               for(int i=l;i<=m;i++){
                if(S[i]==-1)s[i] = 1;   
                }
               int guess = tryCombination(s);
                for(int i=l;i<=m;i++){
                   if(S[i]==-1)s[i] = 0;   
                }
                if(guess<=k && guess!=-1){
                    //esta nessa metade
                    r = m-1;
                    pos = m;
                }else{
                    //outra metade
                    l = m + 1;
                }
            }
            con[pos] = k;  
            S[pos] = 0;
        }else{
            //o certo para ele é 1;
            int l = 0, r = n-1;
            int pos = -1;
            for(int i=0;i<n;i++){
                if(S[i]==-1)s[i] = 1;
            }
            while(l<=r){
               int m = (l+r)>>1;
               for(int i=l;i<=m;i++){
                if(S[i]==-1)s[i] = 0;   
                }
               int guess = tryCombination(s);
                for(int i=l;i<=m;i++){
                   if(S[i]==-1)s[i] = 1;   
                }
                if(guess<=k && guess!=-1){
                    //esta nessa metade
                    r = m-1;
                    pos = m;
                }else{
                    //outra metade
                    l = m + 1;
                }
            }
            con[pos] = k;  
            S[pos] = 1;
            
        }
        
    }
    answer(S,con);
}

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