Submission #1231063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231063		diana	Cave (IOI13_cave)	C++20	100 / 100	242 ms	756 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

const int M = 5e3+3;
bool isKnown[M];
bool value[M];
int place[M], ivx, N;

void initial(int x)
{
    int ask[N] = {};
    for(int i=0; i<x; i++)
        ask[place[i]] = value[i];

    ivx = (tryCombination(ask) == x);
}


void aaa(int x, int l=0, int r=N-1)
{
    if(l == r)
    {
        value[x] = ivx;
        place[x] = l;
        isKnown[place[x]] = 1;
        return;
    }

    int ask[N];
    int mid = (l+r)/2;
    for(int i=0; i<x; i++)
        ask[place[i]] = value[i];

    for(int i=l; i<=mid; i++)
        if(!isKnown[i])
            ask[i] = ivx;
    for(int i=mid+1; i<=r; i++)
        if(!isKnown[i])
            ask[i] = (!ivx);

    int a = tryCombination(ask);
    if(a == x)
        aaa(x, mid+1, r);
    else
        aaa(x, l, mid);
}

void exploreCave(int n)
{
    N = n;
    for(int i=0; i<n; i++)
    {
        initial(i);
        aaa(i);
    }
    int ans1[n], ans2[n];
    for(int i=0; i<n; i++)
        ans1[place[i]] = value[i];
    for(int i=0; i<n; i++)
        ans2[place[i]] = i;
    answer(ans1, ans2);
}

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