Submission #876492

#	Time	Username	Problem	Language	Result	Execution time	Memory
876492		n3rm1n	Cave (IOI13_cave)	C++17	0 / 100	439 ms	492 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
#define endl '\n'
using namespace std;
const int MAXN = 2005;

int n, taken[MAXN], correct[MAXN], connected_to[MAXN];
int curr_try[MAXN];
void help_try_01(int mid)
{
    for (int i = 0; i < mid; ++ i)
        curr_try[i] = 0;
    for (int i = mid+1; i < n; ++ i)
        curr_try[i] = 1;
    for (int i = 0; i < n; ++ i)
    {
        if(taken[i])curr_try[i] = correct[i];
    }
}
void help_try_10(int mid)
{
    for (int i = 0; i < mid; ++ i)
        curr_try[i] = 1;
    for (int i = mid+1; i < n; ++ i)
        curr_try[i] = 0;
    for (int i = 0; i < n; ++ i)
    {
        if(taken[i])curr_try[i] = correct[i];
    }
}
void exploreCave(int N)
{
    n = N;
    for (int door = 0; door < n; ++ door)
    {
        if(tryCombination(correct) > door)
        {
            int l = 0, r = n-1, mid, ans = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
                help_try_01(mid);
                if(tryCombination(curr_try) > door)
                {
                    ans = mid;
                    l = mid - 1;
                }
                else r = mid + 1;
            }
            taken[ans] = 1;
            correct[ans] = 1;
            connected_to[ans] = door;
        }
        else
        {
            int l = 0, r = n-1, mid, ans = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
                help_try_10(mid);
                if(tryCombination(curr_try) > door)
                {
                    ans = mid;
                    l = mid - 1;
                }
                else r = mid + 1;
            }
            taken[ans] = 1;
            correct[ans] = 0;
            connected_to[ans] = door;
        }
    }
    answer(correct, connected_to);
}

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