Submission #1326145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326145		SSKMF	Cave (IOI13_cave)	C++20	100 / 100	148 ms	556 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

void exploreCave (int lungime)
{
    int *tip = new int[lungime];
    int *sir = new int[lungime];
    bool *eliminat = new bool[lungime];
    for (int indice = 0 ; indice < lungime ; indice++)
    {
        vector <int> ramas;
        for (int __indice = 0 ; __indice < lungime ; __indice++) {
            if (!eliminat[__indice])
                { ramas.push_back(__indice); tip[__indice] = 0; }
        }

        const int dorit = (tryCombination(tip) == indice ? 1 : 0);

        while (ramas.size() > 1)
        {
            const int luat = (int)ramas.size() / 2;
            for (int __indice = 0 ; __indice < luat ; __indice++)
                { tip[ramas[__indice]] = 0; }
            for (int __indice = luat ; __indice < (int)ramas.size() ; __indice++)
                { tip[ramas[__indice]] = 1; }

            bool inceput = (dorit == 0);
            const int rezultat = tryCombination(tip);
            if (rezultat == indice)
                { inceput ^= true; }

            vector <int> inlocuitor;
            if (inceput) {
                for (int __indice = 0 ; __indice < luat ; __indice++)
                    { inlocuitor.push_back(ramas[__indice]); }
            } else {
                for (int __indice = luat ; __indice < (int)ramas.size() ; __indice++)
                    { inlocuitor.push_back(ramas[__indice]); }
            }

            ramas = inlocuitor;
        }

        eliminat[ramas[0]] = true;
        tip[ramas[0]] = dorit;
        sir[ramas[0]] = indice;
    }

    answer(tip , sir);
}

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