Submission #820165

#	Time	Username	Problem	Language	Result	Execution time	Memory
820165		PenguinsAreCute	Cave (IOI13_cave)	C++17	100 / 100	579 ms	444 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define worldssmallestviolin(i, a, b) for(int i = a; i < b; i++)

void exploreCave(int N) {
    int somewhere[N], in[N], the[N];
    worldssmallestviolin(universe,0,N) somewhere[universe]=the[universe]=-1;
    worldssmallestviolin(someones,0,N) {
        bool got;
        worldssmallestviolin(it,0,N) in[it]=(bool)the[it];
        int worse=tryCombination(in);
        got=(worse>someones||worse==-1);
        int wish=0,that=N;
        while(that-wish>1) {
            int made=(wish+that)/2;
            worldssmallestviolin(easier,0,N) if(the[easier]==-1) in[easier]=(got==(wish<=easier&&easier<made));
            worse=tryCombination(in);
            if(worse>someones||worse==-1) that=made;
            else wish=made;
        }
        somewhere[wish]=someones, the[wish]=got;
    }
    answer(the,somewhere);
}

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