Submission #774297

#	Time	Username	Problem	Language	Result	Execution time	Memory
774297		teokakabadze	Cave (IOI13_cave)	C++17	100 / 100	312 ms	536 KiB

cave

#include "cave.h"
#define n 50005

int a[n], k, c, l, r, p, i, j, f[n];

void exploreCave(int N) {

    int a[N], d[N];
    for(i = 0; i < N; i++)
    {
        for(j = 0; j < N; j++)
        if(!f[j]) a[j] = 0;
        p = tryCombination(a);
        if(p == i) k = 1;
        else k = 0;

        l = 0, r = N - 1;
        while(l < r)
        {
            c = (l + r) / 2;
            for(j = l; j <= c; j++)
            if(!f[j]) a[j] = 0;
            for(j = c + 1; j <= r; j++)
            if(!f[j]) a[j] = 1;
            p = tryCombination(a);
            if(p == i)
            {
                if(!k) l = c + 1;
                else r = c;
            }
            else
            {
                if(!k) r = c;
                else l = c + 1;
            }
        }
        d[l] = i, a[l] = k, f[l] = 1;
    }
    answer(a, d);
}

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