제출 #548178

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

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

int find_pos(int d, vi& pos, vi& corr)
{
    int n = pos.size();
    vector<int> t(n, 0);
    for (int i = 0; i < d; i++)
        t[pos[i]] = corr[i];

    return tryCombination(t.data()) == d;
}

bool test_range(int b, int e, int d, vi& used, vi& pos, vi& corr)
{
    int n = pos.size();
    vector<int> t(n, 1 - corr[d]);
    for (int i = 0; i < d; i++)
        t[pos[i]] = corr[i];
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (used[i])
            continue;
        if (c >= b && c < e)
            t[i] = corr[d];
        c++;
    }
    return tryCombination(t.data()) != d;
}

void exploreCave(int n)
{
    vi pos(n, -1);
    vi corr(n, -1);
    vi used(n, 0);
    for (int d = 0; d < n; d++) {
        corr[d] = find_pos(d, pos, corr);
        int l = 0;
        int h = n - d - 1;
        while (l < h - 1) {
            int m = (h - l) / 2 + l;
            if (test_range(l, m, d, used, pos, corr))
                h = m;
            else
                l = m;
        }
        pos[d] = l;
    }
    vi S(n);
    for (int i = 0; i < n; i++)
        S[pos[i]] = corr[i];
    answer(S.data(), pos.data());
}

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