제출 #594053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
594053		PoonYaPat	동굴 (IOI13_cave)	C++14	0 / 100	353 ms	432 KiB

cave

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

void exploreCave(int n) {
    int con[5000],test[5000],ans[5000]; // switch i connect to door con[i]
    bool fix_switch[5000];
    memset(fix_switch,0,sizeof(fix_switch));

    for (int i=0; i<n; ++i) { //find door x (0 to x-1 are open)
        for (int j=0; j<n; ++j) if (!fix_switch[j]) test[j]=0;
        int st=tryCombination(test);

        int l=0, r=n-1;

        while (r>l) {
            int mid=(l+r)/2;
            for (int j=0; j<n; ++j) if (!fix_switch[j]) test[j]=0;
            for (int j=mid+1; j<=r; ++j) if (!fix_switch[j]) test[j]=1;

            if (tryCombination(test)==st) r=mid; //not change
            else l=mid+1; //change
        }

        //door i switch r
        con[r]=i;
        fix_switch[r]=true;

        if (st==i) ans[r]=1;
        else ans[r]=0;

        test[r]=ans[r];
    }

    answer(con,ans);
}

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