Submission #548182

#	Time	Username	Problem	Language	Result	Execution time	Memory
548182		Sergio_2357	Cave (IOI13_cave)	C++17	0 / 100	941 ms	444 KiB

cave

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

using namespace std;

typedef vector<int> vi;

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

    return tryCombination(t) == d;
}

bool test_range(int b, int e, int d, vi& used, int* pos, vi& corr)
{
    int n = corr.size();
    int t[n];
    for (int i = 0; i < n; i++)
        t[i] = 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) != d;
}

void exploreCave(int n)
{
    int pos[n];
    for (int i = 0; i < n; i++)
        pos[i] = -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;
    }
    int S[n];
    for (int i = 0; i < n; i++)
        S[pos[i]] = corr[i];
    answer(S, pos);
}

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