제출 #1333397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1333397		piolk	동굴 (IOI13_cave)	C++20	100 / 100	551 ms	528 KiB

cave

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

int S[5000],D[5000],curr[5000];

void exploreCave(int n){
    for (int i=0;i<n;i++){
        D[i]=-1;
    }

    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (D[j]==-1) curr[j]=0;
            else curr[j]=S[j];
        }
        int door=tryCombination(curr);

        int cor=0;
        if (door==i) cor=1;

        int l=0;
        int r=n-1;
        int ans=0;

        while (l<=r){
            int mid=(l+r)/2;

            for (int j=0;j<n;j++){
                if (D[j]!=-1){
                    curr[j]=S[j];
                    continue;
                }
                if (j>=l && j<=mid) curr[j]=cor;
                else curr[j]=(cor^1);
            }

            door=tryCombination(curr);

            if (door==i){
                l=mid+1;
            } else {
                ans=mid;
                r=mid-1;
            }
        }

        D[ans]=i;
        S[ans]=cor;
    }

    answer(S,D);
}

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