Submission #465201

#	Time	Username	Problem	Language	Result	Execution time	Memory
465201		sumitvivek_001	Cave (IOI13_cave)	C++14	100 / 100	1209 ms	544 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
 
int c[5005], d[5005];
 
int generate(int l, int r, int n, bool curval)
{
    int cur[n];
    for(int i=0; i<l; i++) cur[i]=!curval;
    for(int i=l; i<=r; i++) cur[i]=curval;
    for(int i=r+1; i<n; i++) cur[i]=!curval;
    
    for(int i=0; i<n; i++)
        if(d[i]!=-1) cur[i]=c[i];
 
    int x=tryCombination(cur);
    return x;
}
 
void exploreCave(int n)
{
    memset(d, -1, sizeof(d));
    bool curval;
    for(int i=0; i<n; i++)
    {
        if(generate(0, n-1, n, 0)==i) curval=1;
        else curval=0;
 
        int l=0, r=n-1, mid;
        while(l<=r)
        {
            mid=(l+r)>>1;
            //int x=generate(l, mid, n, curval);
            //cout<<i<<' '<<curval<<' '<<l<<' '<<r<<' '<<mid<<' '<<x<<endl;
            if(generate(l, mid, n, curval)==i) l=mid+1;
            else r=mid-1;
        }
        c[l]=curval;
        d[l]=i;
    }
    answer(c, d);
}

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