Submission #962786

#	Time	Username	Problem	Language	Result	Execution time	Memory
962786		NValchanov	Cave (IOI13_cave)	C++17	100 / 100	554 ms	600 KiB

cave

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

using namespace std;
typedef long long ll;

const ll MAXN = 5000;

int door[MAXN];
int pos[MAXN];
ll n;

void flip_pos(ll to)
{
    for(int i = 0; i <= to; i++)
    {
        if(door[i] == -1)
            pos[i] ^= 1;
    }
}

void init_switches()
{
    for(int i = 0; i < n; i++)
    {
        door[i] = -1;
        pos[i] = 0;
    }
}

bool check(ll k, ll i)
{
    flip_pos(k);
    ll cur = tryCombination(pos);
    flip_pos(k);

    return cur == i;
}

void exploreCave(int N)
{
    n = N;
    init_switches();

    for(int i = 0; i < n; i++)
    {
        ll cur = tryCombination(pos);

        if(cur == i)
            flip_pos(n - 1);

        ll left = 0;
        ll right = n - 1;
        ll ans = -1;
        ll mid;
        while(left <= right)
        {
            mid = (left + right) / 2;
            if(check(mid, i))
            {
                right = mid - 1;
                ans = mid;
            }
            else
                left = mid + 1;
        }
        door[ans] = i;
    }
    answer(pos, door);
}

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