Submission #470137

#	Time	Username	Problem	Language	Result	Execution time	Memory
470137		Newtech66	Cave (IOI13_cave)	C++17	0 / 100	595 ms	420 KiB

cave

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

int recurse(vector<int>& guess,int pos,const vector<int>& door,const vector<int>& setting,int l,int r,int N) //in [l,r)
{
    if(l==r)    return l;
    int mid=l+(r-l)/2;
    fill(guess.begin()+l,guess.begin()+mid,1);
    for(int i=0;i<N;i++)
    {
        if(door[i]!=-1)
        {
            guess[door[i]]=setting[i];
        }
    }
    int next=tryCombination(guess.data());
    if(next==pos)
    {
        if(setting[pos]==0)
        {
            fill(guess.begin()+l,guess.begin()+mid,0);
            return recurse(guess,pos,door,setting,l,mid,N);
        }else
        {
            return recurse(guess,pos,door,setting,mid,r,N);
        }
    }else
    {
        if(setting[pos]==0)
        {
            return recurse(guess,pos,door,setting,mid,r,N);
        }else
        {
            fill(guess.begin()+l,guess.begin()+mid,0);
            return recurse(guess,pos,door,setting,l,mid,N);
        }
    }
}

void exploreCave(int N) {
    vector<int> door(N,-1),setting(N,-1);
    for(int i=0;i<N;i++)
    {
        vector<int> guess(N);
        fill(guess.begin(),guess.end(),0);
        for(int i=0;i<N;i++)
        {
            if(door[i]!=-1)
            {
                guess[door[i]]=setting[i];
            }
        }
        int next=tryCombination(guess.data());
        setting[i]=(next==i);
        door[i]=recurse(guess,i,door,setting,0,N,N);
    }
    answer(setting.data(),door.data());
}

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