Submission #548173

#	Time	Username	Problem	Language	Result	Execution time	Memory
548173		Sergio_2357	Cave (IOI13_cave)	C++14	0 / 100	1025 ms	448 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[0]) == 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[0]) != 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[0], &pos[0]);
}

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