제출 #1214668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214668		hgmhc	동굴 (IOI13_cave)	C++20	51 / 100	155 ms	496 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 (tryCombination(S) == i) {
            S[x] ^= 1;
        }
    }
    answer(S, D);
}

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