제출 #1283170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283170		cokalhado	동굴 (IOI13_cave)	C++20	100 / 100	103 ms	508 KiB

cave

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

// we are looking at door i, find the switch that unlocks it (is in interval [l, r])
void find(int S[], int D[], bool found[], int N, int l, int r, int i, int prev = -2)
{
    int x;
    if(prev == -2) x = tryCombination(S);
    else x = prev;
    bool ans1 = 0;
    if(x == i)
    {
        ans1 = 1;
    }

    if(l == r)
    {
        if(ans1) S[l] = 1-S[l];
        found[l] = 1;
        D[l] = i;
        return;
    }

    int m = (l+r)/2;
    for(int j = l; j <= m; j++)
    {
        if(!found[j]) S[j] = 1-S[j];
    }
    x = tryCombination(S);
    bool ans2 = 0;
    if(x == i)
    {
        ans2 = 1;
    }
    if(ans1 == ans2) find(S, D, found, N, m+1, r, i, x);
    else find(S, D, found, N, l, m, i, x);
}

void exploreCave(int N) {
    int S[N] = {0};
    int D[N] = {0};
    bool found[N] = {0};

    for(int i = 0; i < N; i++)
    {
        find(S, D, found, N, 0, N-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