제출 #1359612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359612		raineyj	동굴 (IOI13_cave)	C++20	100 / 100	200 ms	536 KiB

cave

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

void exploreCave(int N)
{
    int s[N], d[N], dts[N];
    for(int i=0; i<N; i++)
    {
        s[i]=0;
        dts[i]=0;
    }
    for(int i=0; i<N; i++)
    {
        int c[N];
        for(int j=0; j<N; j++) c[j]=0;
        for(int j=0; j<i; j++) c[dts[j]]=s[dts[j]];
        int cs;
        if(tryCombination(c)!=i) cs=0;
        else cs=1;
        int l=0, r=N-1;
        while(l<r)
        {
            int m=(l+r)/2;
            for(int j=0; j<N; j++) c[j]=cs;
            for(int j=l; j<=m; j++) c[j]=1-cs;
            for(int j=0; j<i; j++) c[dts[j]]=s[dts[j]];
            if(tryCombination(c)==i)
            {
                r=m;
            }
            else
            {
                l=m+1;
            }
        }
        s[l]=cs;
        d[l]=i;
        dts[i]=l;
    }
    answer(s, d);
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 13 / 13
• 서브태스크 3: 21 / 21
• 서브태스크 4: 30 / 30
• 서브태스크 5: 24 / 24