Submission #1081186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081186		clementine	Cave (IOI13_cave)	C++17	0 / 100	37 ms	600 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
    int n = N;
    int s = 0, e = 0;
    int tri[n];
    int ans[n];
    int gate[n];
    fill(ans, ans + n, -1);
    fill(gate, gate +n, -1);
    int val = 1, notval = 0;
    while(s != n)
    {
        if(val == 1)
        {
            val = 0;
            notval = 1;
        }
        else
        {
            val = 1;
            notval = 0;
        }
        for(int i = 0; i < n; i ++)
        {
            if(ans[i] == -1)
            {
                tri[i] = val;
            }
            else
            {
                tri[i] = ans[i];
            }
        }
        e = tryCombination(tri);
        if(e == -1)
        {
            e = n;
        }
        for(int sp = s; sp < e; sp ++)
        {
            int l = 0, r = n-1;
            while(l != r)
            {
                int mid = (l + r) / 2;
                int temp[n];
                for(int i = l; i <= mid; i ++)
                {
                    if(ans[i] == -1)
                    {
                        temp[i] = val;
                    }
                    else 
                    {
                        temp[i] = ans[i];
                    }
                }
                for(int i = mid + 1; i <=r; i ++)
                {
                    if(ans[i] == -1)
                    {
                        temp[i] = notval;
                    }
                    else 
                    {
                        temp[i] = ans[i];
                    }
                }
                int res = tryCombination(temp);
                if( res > s)
                {
                    r = mid;
                }
                else
                {
                    l = mid + 1;
                }
            }
            gate[sp] = l;
            ans[l] = val;
        }
        s = e;
    }

    answer(ans, gate);

}

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