Submission #1340255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340255		nathlol2	Cave (IOI13_cave)	C11	0 / 100	140 ms	520 KiB

cave

#include "cave.h"
#include <string.h>

void exploreCave(int n){
    int c[n], t[n];
    memset(t, -1, sizeof t);
    for(int i = 0;i<n;i++){
        int z[n];
        memset(z, -1, sizeof z);
        int v[n], sz = 0;
        for(int j = 0;j<n;j++){
            if(t[j] != -1) z[t[j]] = c[j];
        }
        for(int j = 0;j<n;j++){
            if(z[j] == -1) z[j] = 0, v[sz++] = j;
        }
        int T = tryCombination(z);
        int tt = (T == -1 || T > i);
        int l = 0, r = sz - 1;
        while(l < r){
            int md = (l + r) / 2;
            for(int j = 0;j<sz;j++){
                if(j <= md) z[v[j]] = tt;
                else z[v[j]] = (tt ^ 1);
            }
            T = tryCombination(z);
            if(T == -1 || T > i){
                r = md;
            }else{
                l = md + 1;
            }
        }
        c[v[r]] = tt;
        t[i] = v[r];
    }
    answer(c, t);
}

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