제출 #876508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876508		n3rm1n	동굴 (IOI13_cave)	C++17	0 / 100	281 ms	500 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
#define endl '\n'
using namespace std;
const int MAXN = 5005;

int n, taken[MAXN], correct[MAXN], connected_to[MAXN];
int curr_try[MAXN];
void help_try_01(int mid)
{
    for (int i = 0; i < mid; ++ i)
        curr_try[i] = 0;
    for (int i = mid; i < n; ++ i)
        curr_try[i] = 1;
    for (int i = 0; i < n; ++ i)
    {
        if(taken[i])curr_try[i] = correct[i];
    }
}
void help_try_10(int mid)
{
    for (int i = 0; i < mid; ++ i)
        curr_try[i] = 1;
    for (int i = mid; i < n; ++ i)
        curr_try[i] = 0;
    for (int i = 0; i < n; ++ i)
    {
        if(taken[i])curr_try[i] = correct[i];
    }
}
void exploreCave(int N)
{
    n = N;
    for (int door = 0; door < n; ++ door)
    {
        if(tryCombination(correct) > door || tryCombination(correct) == -1)
        {
            int l = 0, r = n-1, mid, ans = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
                help_try_01(mid);
                int res = tryCombination(curr_try);
                if(res >= door || res == -1)
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            taken[ans] = 1;
            correct[ans] = 1;
            connected_to[ans] = door;
        }
        else
        {
            int l = 0, r = n-1, mid, ans = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
                help_try_10(mid);
                int res = tryCombination(curr_try);
                if(res >= door || res == -1)
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            taken[ans] = 1;
            correct[ans] = 0;
            connected_to[ans] = door;
        }
    }
    answer(correct, connected_to);
}

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