Submission #1303597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303597		activedeltorre	Cave (IOI13_cave)	C++20	100 / 100	284 ms	696 KiB

cave

#include "cave.h"
#include<iostream>
#include <vector>
using namespace std;
int n;
int query(vector<pair<int,int> >stiut,vector<int>nestiut,int prefix1)
{
    int rasp[5005];
    for(int i=0; i<n; i++)
    {
        rasp[i]=0;
    }
    for(int i=0; i<prefix1; i++)
    {
        rasp[nestiut[i]]=1;
    }
    for(auto k:stiut)
    {
        rasp[k.first]=k.second;
    }
    int last=tryCombination(rasp);
    if(last==-1)
    {
        return n;
    }
    return last;
}
void exploreCave(int N)
{
    vector<pair<int,int>>stiut;
    vector<int>nestiut;
    n=N;
    for(int i=0; i<n; i++)
    {
        nestiut.push_back(i);
    }
    int tip[5005],rasp[5005];
    for(int i=1; i<=n; i++)
    {
        int rez=query(stiut,nestiut,nestiut.size());
        if(rez>=i)
        {
            int st=0,dr=nestiut.size(),sol=0;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                rez=query(stiut,nestiut,mij);
                if(rez>=i)
                {
                    dr=mij-1;
                    sol=mij-1;
                }
                else
                {
                    st=mij+1;
                }
            }
            sol=nestiut[sol];
            rasp[sol]=i-1;
            tip[sol]=1;
            //cout<<"usa "<<i-1<<" descisa de switchul "<<sol<<" pe 1"<<'\n';
            stiut.push_back({sol,1});
            vector<int>ne2;
            for(auto k:nestiut)
            {
                if(k!=sol)
                {
                    ne2.push_back(k);
                }
            }
            swap(ne2,nestiut);
        }
        else
        {
            int st=0,dr=nestiut.size(),sol=0;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                rez=query(stiut,nestiut,mij);
                if(rez>=i)
                {
                    st=mij+1;
                }
                else
                {
                    dr=mij-1;
                    sol=mij-1;
                }
            }
            sol=nestiut[sol];
            tip[sol]=0;
            rasp[sol]=i-1;
            //cout<<"usa "<<i-1<<" descisa de switchul "<<sol<<" pe 0"<<'\n';
            stiut.push_back({sol,0});
            vector<int>ne2;
            for(auto k:nestiut)
            {
                if(k!=sol)
                {
                    ne2.push_back(k);
                }
            }
            swap(ne2,nestiut);
        }
    }
    answer(tip,rasp);

}

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