Submission #1364146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1364146		abgfd324	동굴 (IOI13_cave)	C++20	12 / 100	211 ms	532 KiB

cave

#include<iostream>
#include<vector>
#include"cave.h"
using namespace std;
int S[5001], D[5001];
int curS[5001];
bool prc[5001];
void exploreCave(int N)
{
    fill(S, S+5000, 0);
    fill(D, D+5000, 0);
    fill(curS, curS+5000, 0);
    fill(prc, prc+5000, false);
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(prc[j]) curS[j] = S[j];
            else curS[j] = 0;
        }
        int open;
        int cur = tryCombination(curS);
        if(cur > i || cur == -1) open = 0;
        else open = 1;
        int l = 0, r = N-1;
        while(l < r)
        {
            int m = (l+r)/2;
            for(int i = 0; i < N; i++)
            {
                if(prc[i]) curS[i] = S[i];
                else
                {
                    if(i <= m) curS[i] = open;
                    else curS[i] = abs(open-1);
                }
            }
            int ans = tryCombination(curS);
            if(ans > i || ans == -1) r = m;
            else l = m+1;
        }
        prc[l] = true;
        S[i] = open;
        D[i] = l;
    }
    answer(S, D);
}

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