Submission #852874

#	Time	Username	Problem	Language	Result	Execution time	Memory
852874		Bach21	Cave (IOI13_cave)	C++14	0 / 100	207 ms	540 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int nmax=5e3+5;
int qarr[nmax],check[nmax],res[nmax],res1[nmax];
int N;
bool checker(int tmp,int tar)
{
    if (tmp==-1) return 1;
    return (tmp>tar);
}
void solve(int tar,int l,int r,int known)
{
    if (l==r)
    {
        res[l]=known;
        check[l]=1;
        res1[l]=tar;
    }
    memset(qarr,0,sizeof qarr);
    int mid=(l+r) >> 1;
    for (int i=0;i<N;i++)
    {
        if (i>=l && i<=mid)
        {
            qarr[i]=known;
        } else
            qarr[i]=1^known;
    }
    for (int i=0;i<N;i++)
    {
        if (check[i]) qarr[i]=res[i];
    }
    int ans=tryCombination(qarr);
    if (checker(ans,tar))
    {
        solve(tar,l,mid,known);
    } else solve(tar,mid+1,r,known);
}
int findcolor(int tar)
{
    memset(qarr,0,sizeof qarr);
    for (int i=0;i<N;i++)
    {
        if (check[i]) qarr[i]=res[i];
    }
    int ans=tryCombination(qarr);
    if (checker(ans,tar)) return 0; else return 1;
}
void exploreCave(int n)
{
    int N=n;
    for (int i=0;i<N;i++)
    {
        int color= findcolor(i);
        solve(i,0,N-1,color);
    }
    answer(res,res1);
}

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