제출 #383700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383700		LittleCube	동굴 (IOI13_cave)	C++14	100 / 100	911 ms	644 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], attempt[5005], S[5005], D[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 = 0; j < l; j++)
        if (comb[j] != -1)
            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] = comb[j];
    int verdict = tryCombination(attempt);
    //for (int i = 0; i < n;i++)
    //    cerr << attempt[i] << " ";
    //cerr << "  " << verdict << '\n';
    //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 j = 0; j < n; j++)
            if (comb[j] == -1)
                attempt[j] = 0;
            else
                attempt[j] = comb[j];
                
        int verdict = tryCombination(attempt), state, pos;
        if (verdict == i)
            state = 1;
        else
            state = 0;
        pos = bs(0, n - 1, i, state);
        //cerr << i << "->" << pos << ":" << state << '\n';
        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: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24