Submission #99796

#	Time	Username	Problem	Language	Result	Execution time	Memory
99796		MohamedAhmed0	Cave (IOI13_cave)	C++14	0 / 100	61 ms	516 KiB

cave

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

    using namespace std ;

    const int MAX = 5005 ;
    int s[MAX] , d[MAX] , arr[MAX] , last , done[MAX];
    int now ;

    bool check(int l , int mid)
    {
        for(int i = l ; i <= mid ; ++i)
        {
            if(done[i])
                continue ;
            s[i] = !s[i] ;
        }
        int x = tryCombination(s) ;
        for(int i = l ; i <= mid ; ++i)
        {
            if(done[i])
                continue;
            s[i] = !s[i] ;
        }
        if(x > now || x == -1)
        {
            last = x ;
            return 1 ;
        }
        return 0 ;
    }

    void exploreCave(int N)
    {
        memset(s , 0 , sizeof(s));
        for(int i = 0 ; i < N ; ++i)
        {
            now = i ;
            if(last > i || last == -1)
            {
                for(int j = 0 ; j < N ; ++j)
                {
                    if(done[j])
                        continue;
                    s[j] = !s[j] ;
                }
            }
            int l = 0 , r = N-1 , ans = N-1;
            while(l <= r)
            {
                int mid = (l + r) / 2 ;
                if(check(l , mid))
                    ans = mid , r = mid-1 ;
                else
                    l = mid+1 ;
            }
            d[i] = ans ;
            done[ans] = 1 ;
            s[ans] = !s[ans] ;
        }
        answer(s , d) ;
    }

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