Submission #995942

#	Time	Username	Problem	Language	Result	Execution time	Memory
995942		daffuwu	Cave (IOI13_cave)	C++14	100 / 100	224 ms	592 KiB

cave

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

int s[5069], d[5069], unk[5069], lo, hi, mi;

int conv(int x)
{
    if (x == -1) return 5001;
    return x;
}

void exploreCave(int n) 
{
    int i, j, m;
    //mulai dari 000000
    //d[i] --> switch i door apa
    //unk --> array yang buat switch apa aja yang belum tahu connect ke door apa (unknown)
    for (i=0; i<=n-1; i++) s[i] = 0;
    for (i=0; i<=n-1; i++) d[i] = -1;
    //tentuin tiap door dari 0, 1, ... n-1 switchnya apa
    for (i=0; i<=n-1; i++)
    {
        for (j=0, m=-1; j<=n-1; j++)
        {
            if (d[j] == -1) unk[++m] = j;
        }
        if (tryCombination(s) != i)
        {
            //flip semua switch unkwon, karena switch unknown connect ke door yang indeksnya >=i
            for (j=0; j<=m; j++) s[unk[j]] ^= 1;
        }
        //pasti switch yang connect ke door i ketutup boz (tryCombination(s) == i)
        //tinggal daffanandabinser mainin switch yang unknown, switch mana nich yang connect ke door i
        for (lo=0, hi=m; lo<=hi; )
        {
            mi = (lo+hi)/2;
            for (j=0; j<=mi; j++) s[unk[j]] ^= 1;
            if (conv(tryCombination(s))>i) hi = mi-1; //yang paling kiri dan door i kebuka adalah switchnya :D
            else lo = mi+1;
            for (j=0; j<=mi; j++) s[unk[j]] ^= 1;
        }
        s[unk[hi+1]] ^= 1;
        d[unk[hi+1]] = i;
    }
    answer(s, d);
}

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