Submission #1214670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214670		hgmhc	Cave (IOI13_cave)	C++20	100 / 100	161 ms	500 KiB

cave

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

int S[5000];
int D[5000];
bool fixed[5000];

bool pre;
bool ok(int l, int r, int i) {
    for(int i=l; i<=r; ++i) if(!fixed[i]) S[i] ^= 1;
    bool cur = tryCombination(S)==i;
    for(int i=l; i<=r; ++i) if(!fixed[i]) S[i] ^= 1;
    return pre != cur;
}

void exploreCave(int n) {
    for(int i=0; i<n; ++i) {
        int x=0, y=n-1, z;
        pre = tryCombination(S)==i;
        while(x<y) {
            z=(x+y)>>1;
            if(ok(x,z,i)) y=z;
            else x=z+1;
        }
        assert(x==y);
        D[x] = i;
        fixed[x] = true;
        if (pre) S[x] ^= 1;
    }
    answer(S, D);
}

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