Submission #882358

#	Time	Username	Problem	Language	Result	Execution time	Memory
882358		pirhosig	Cave (IOI13_cave)	C++17	100 / 100	683 ms	860 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define R(a)  for (int i = 0; i < a; ++i)
#define RR(a) for (int j = 0; j < a; ++j)
using namespace std;


bool testDoor(int swit[], int door)
{
    int res = tryCombination(swit);
    if (door < res || res == -1) return true;
    else return false;
}


void exploreCave(int N) {
    int sPoses[N];
    int switchStates[N];
    int doorStates[N];
    R(N)
    {
        sPoses[i] = -1;
        switchStates[i] = -1;
        doorStates[i] = -1;
    }

    R(N)
    {
        bool zero = false;
        if (doorStates[i] == -1)
        {
            int initialTestSwitches[N];
            RR(N)
            {
                if (switchStates[j] == -1) initialTestSwitches[j] = 0;
                else initialTestSwitches[j] = switchStates[j];
            }

            int res = tryCombination(initialTestSwitches);
            if (res == -1)
            {
                zero = true;
                for (int j = i; j < N; ++j)
                {
                    doorStates[j] = 0;
                }
            }
            else if (i < res)
            {
                zero = true;
                for (int j = i; j < res; ++j)
                {
                    doorStates[j] = 0;
                }
            }
        }
        else zero = true;

        if (zero)
        {
            int lower = 0;
            int upper = N - 1;
            int definite = -1;
            while (upper - lower > 1)
            {
                int mid = (lower + upper) / 2;
                int testSwitches[N];
                RR(N)
                {
                    if (switchStates[j] != -1) testSwitches[j] = switchStates[j];
                    else
                    {
                        if (lower <= j && j <= mid) testSwitches[j] = 0;
                        else testSwitches[j] = 1;
                    }
                }

                if (testDoor(testSwitches, i))
                {
                    upper = mid;
                }
                else
                {
                    lower = mid;
                    if (lower + 1 == upper) definite = upper;
                }
            }

            if (definite > -1)
            {
                sPoses[i] = definite;
                switchStates[definite] = 0;
            }
            else
            {
                int testSwitches[N];
                RR(N)
                {
                    if (switchStates[j] != -1) testSwitches[j] = switchStates[j];
                    else
                    {
                        if (j == lower) testSwitches[j] = 0;
                        else testSwitches[j] = 1;
                    }
                }

                if (testDoor(testSwitches, i))
                {
                    sPoses[i] = lower;
                    switchStates[lower] = 0;
                }
                else
                {
                    sPoses[i] = upper;
                    switchStates[upper] = 0;
                }
            }

        }
        else
        {
            int lower = 0;
            int upper = N - 1;
            int definite = -1;
            while (upper - lower > 1)
            {
                int mid = (lower + upper) / 2;
                int testSwitches[N];
                RR(N)
                {
                    if (switchStates[j] != -1) testSwitches[j] = switchStates[j];
                    else
                    {
                        if (lower <= j && j <= mid) testSwitches[j] = 1;
                        else testSwitches[j] = 0;
                    }
                }

                if (testDoor(testSwitches, i))
                {
                    upper = mid;
                }
                else
                {
                    lower = mid;
                    if (lower + 1 == upper) definite = upper;
                }
            }

            if (definite > -1)
            {
                sPoses[i] = definite;
                switchStates[definite] = 1;
            }
            else
            {
                int testSwitches[N];
                RR(N)
                {
                    if (switchStates[j] != -1) testSwitches[j] = switchStates[j];
                    else
                    {
                        if (j == lower) testSwitches[j] = 1;
                        else testSwitches[j] = 0;
                    }
                }

                if (testDoor(testSwitches, i))
                {
                    sPoses[i] = lower;
                    switchStates[lower] = 1;
                }
                else
                {
                    sPoses[i] = upper;
                    switchStates[upper] = 1;
                }
            }
        }

    }

    int switchesForDoors[N];
    R(N)
    {
       switchesForDoors[sPoses[i]] = i;
    }

    /*R(N)
    {
        cout << switchesForDoors[i] << " ";
    }
    cout << endl;
    R(N)
    {
        cout << switchStates[i] << " ";
    }
    cout << endl;*/

    answer(switchStates, switchesForDoors);
}

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