Submission #383691

#	Time	Username	Problem	Language	Result	Execution time	Memory
383691		LittleCube	Cave (IOI13_cave)	C++14	25 / 100	550 ms	620 KiB

cave

/*  | |       _    _  | |        _____       | |
//  | |   _  | |  | | | | _____ /  ___|__  __| |___  _____
//  | |  |_|[   ][   ]| |/  _  \| |    | | | |  _  \/  _  \  
//  | L__| | | |_ | |_| || ____|| |___ | |_| | |_| || ____|
//  L____|_| |___||___|_|\_____|\_____|\_____/\____/\_____|
//  Segment Tree is hard.
*/
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
//#pragma pack(0)
//#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
//#define S second
#define pb(x) emplace_back(x)
#define MOD 1000000007
#define MOD2 998244353
#define _INFINITY 9223372036854775807
//#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

#include "cave.h"

int n, comb[5005], match[5005];

int bs(int l, int r, int i, int state)
{
    if (l == r)
        return l;
    int mid = (l + r) / 2;
    int *attempt = new int[n];

    for (int j = 1; j < l; j++)
        if (comb[j] == -1)
            attempt[j] = state ^ 1;
        else
            attempt[j] = comb[j];
    for (int j = l; j <= mid; j++)
        if (comb[j] == -1)
            attempt[j] = state;
        else
            attempt[j] = comb[j];
    for (int j = mid + 1; j <= r; j++)
        if (comb[j] == -1)
            attempt[j] = state ^ 1;
        else
            attempt[j] = comb[j];
    for (int j = r + 1; j < n; j++)
        if (comb[j] == -1)
            attempt[j] = state ^ 1;
        else
            attempt[j] = comb[j];
    int verdict = tryCombination(attempt);
    delete[] attempt;
    if (verdict == i)
        return bs(mid + 1, r, i, state);
    else
        return bs(l, mid, i, state);
}

void exploreCave(int N)
{
    n = N;
    for (int i = 0; i < n; i++)
        match[i] = comb[i] = -1;

    for (int i = 0; i < n; i++)
    {
        int *attempt = new int[n];
        for (int i = 0; i < n; i++)
            if (comb[i] == -1)
                attempt[i] = 0;
            else
                attempt[i] = comb[i];
        int verdict = tryCombination(attempt), state, pos;
        if (verdict == i)
            state = 1;
        else
            state = 0;
        pos = bs(0, n - 1, i, state);
        comb[pos] = state;
        match[pos] = i;
        delete[] attempt;
    }
    int *S = new int[n];
    int *D = new int[n];
    for (int i = 0; i < n; i++)
        S[i] = comb[i], D[i] = match[i];
    answer(S, D);
    delete[] S;
    delete[] D;
}

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