Submission #470139

#	Time	Username	Problem	Language	Result	Execution time	Memory
470139		Newtech66	Cave (IOI13_cave)	C++17	100 / 100	1122 ms	548 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(r-l==1)    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];
            }
        }
        //for(auto& e:guess)  cout<<e<<" ";
        //cout<<endl;
        int next=tryCombination(guess.data());
        //cout<<i<<" "<<next<<endl;
        setting[i]=(next==i);
        door[i]=recurse(guess,i,door,setting,0,N,N);
    }
    vector<int> invdoor(N),invset(N);
    for(int i=0;i<N;i++)
    {
        invdoor[door[i]]=i;
        invset[door[i]]=setting[i];
    }
    answer(invset.data(),invdoor.data());
}

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