Submission #632581

#	Time	Username	Problem	Language	Result	Execution time	Memory
632581		Stavab	Cave (IOI13_cave)	C++14	100 / 100	183 ms	460 KiB

cave

#include "cave.h"
 
void exploreCave(int n)
{
    int S[n], D[n];
    
    for(int i = 0; i < n; i++)
    {
        S[i] = 0;
        D[i] = -1;
    }
    
    int cur, prev, comb;
    for(int i = 0; i < n; i++)
    {
        comb = tryCombination(S);
        if(comb > i || comb == -1)
            prev = 1;
        else
            prev = 0;
        
        int low = 0;
        int high = n - 1;
        while(high - low > 1)
        {
            int middle = (low + high) / 2;
            
            for(int j = low; j <= middle; j++)
            {
                if(D[j] == -1)
                {
                    if(S[j] == 0)
                        S[j] = 1;
                    else
                        S[j] = 0;
                }
            }
            
            comb = tryCombination(S);
            if(comb > i || comb == -1)
                cur = 1;
            else
                cur = 0;
                
            if(cur == prev)
                low = middle + 1;
            else
                high = middle;
                
            prev = cur;
        }
        
        if(D[low] == -1)
        {
            if(S[low] == 0)
                S[low] = 1;
            else
                S[low] = 0;
                
            comb = tryCombination(S);
            if(comb > i || comb == -1)
                cur = 1;
            else
                cur = 0;
                
            if(cur == prev)
            {
                D[high] = i;
                if(comb == i)
                {
                    if(S[high] == 0)
                        S[high] = 1;
                    else
                        S[high] = 0;
                }
            }
            else
            {
                D[low] = i;
                if(comb == i)
                {
                    if(S[low] == 0)
                        S[low] = 1;
                    else
                        S[low] = 0;
                }
            }
        }
        else
        {
            D[high] = i;
            
            if(comb == i)
            {
                if(S[high] == 0)
                    S[high] = 1;
                else
                    S[high] = 0;
            }
        }
    }
    
    answer(S, D);
}

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