Submission #835031

#	Time	Username	Problem	Language	Result	Execution time	Memory
835031		AndrijaM	Cave (IOI13_cave)	C++14	0 / 100	233 ms	420 KiB

cave

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

const long long mod=1e9+7;
const long long maxn=2e5+10;
const long long logn=20;

long long di[8]={-1,-1,0,1,1,1,0,-1};
long long dj[8]={0,1,1,1,0,-1,-1,-1};


void exploreCave(int n)
{
    int a[n];
    int s[n];
    bool vis[n];
    memset(vis,0,sizeof vis);
    int d[n];
    int pr=-1;
    for(int i=0;i<n;i++)
    {
        for(int ci=0;ci<n;ci++)
        {
            a[ci]=s[ci];
        }
        int p=tryCombination(a);
        if(p==pr)
        {
            int sw=0;
            int l=0;
            int r=n;
            while(l<r)
            {
                int mid=l+(r-l)/2;
                for(int ci=0;ci<n;ci++)
                {
                    a[ci]=s[ci];
                }
                for(int idx=mid;idx<r;idx++)
                {
                    if(!vis[idx])
                    {
                        a[idx]=sw;
                    }
                }
                int pom=tryCombination(a);
                if(pom>p)
                {
                    l=mid+1;
                }
                else
                {
                    r=mid;
                }
            }
            vis[l]=1;
            s[l]=sw;
            d[i]=l;
        }
        else
        {
            int sw=1;
            int l=0;
            int r=n;
            while(l<r)
            {
                int mid=l+(r-l)/2;
                for(int ci=0;ci<n;ci++)
                {
                    a[ci]=s[ci];
                }
                for(int idx=mid;idx<r;idx++)
                {
                    if(!vis[idx])
                    {
                        a[idx]=sw;
                    }
                }
                int pom=tryCombination(a);
                if(pom>p)
                {
                    l=mid+1;
                }
                else
                {
                    r=mid;
                }
            }
            vis[l]=1;
            s[l]=sw;
            d[i]=l;
        }
    }
    answer(s,d);
}

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