Submission #548190

#	Time	Username	Problem	Language	Result	Execution time	Memory
548190		Sergio_2357	Cave (IOI13_cave)	C++17	100 / 100	1772 ms	468 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 = 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) ? 1 : 0;
}

bool test_range(int b, int e, int d, vi& used, vi& 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++) {
        //cout << i << ' ' << c << endl;
        if (used[i])
            continue;
        if (c >= b && c < e)
            t[i] = corr[d];
        c++;
    }
    return tryCombination(t) != 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);
        //cout << d << ' ' << corr[d] << endl;
        int l = 0;
        int h = n - d;
        while (l < h - 1) {
            int m = (h - l) / 2 + l;
            if (test_range(l, m, d, used, pos, corr))
                h = m;
            else
                l = m;
        }
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (used[i])
                continue;
            if (c == l) {
                pos[d] = i;
                used[i] = 1;
            }
            c++;
        }
    }
    int S[n];
    int D[n];
    for (int i = 0; i < n; i++) {
        //cout << corr[i] << ' ' << pos[i] << endl;
        S[pos[i]] = corr[i];
    }
    for (int i = 0; i < n; i++)
        D[pos[i]] = i;
    answer(S, D);
}

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