Submission #1248082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248082		denislav	Cave (IOI13_cave)	C++20	100 / 100	163 ms	516 KiB

cave

# include <iostream>
# include <vector>
using namespace std;
# include "cave.h"
//# include "grader.c"

const int MAX=5e3+11;

/*
int n;
int _S[MAX];
int _D[MAX];
int _pos[MAX];

void read()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>_S[i];
    for(int i=0;i<n;i++)
    {
        cin>>_D[i];
        _pos[_D[i]]=i;
    }
}

int tryCombination(int s[])
{
    for(int i=0;i<n;i++)
    {
        int id=_pos[i];
        if(s[id]!=_S[id]) return i;
    }
    return -1;
}

void answer(int s[], int d[])
{
    bool f=1;
    for(int i=0;i<n;i++)
    {
        if(s[i]!=_S[i]) f=0;
        if(d[i]!=_D[i]) f=0;
    }

    for(int i=0;i<n;i++) cout<<s[i]<<" ";
    cout<<endl;
    for(int i=0;i<n;i++) cout<<d[i]<<" ";
    cout<<endl;

    if(f) cout<<"Correct"<<endl;
    else cout<<"Incorrect"<<endl;
}
*/

///----------------------------------

int s[MAX];
int d[MAX];

int query(int S[])
{
    int resp=tryCombination(S);
    if(resp==-1) return 1e9;
    else return resp;

}

void exploreCave(int N)
{
    for(int i=0;i<N;i++)
    {
        s[i]=0;
        d[i]=-1;
    }

    for(int i=0;i<N;i++)
    {
        int resp=query(s);
        int l=0,r=N-1,ans=0;
        while(l<r)
        {
            int mid=(l+r)/2;
            for(int j=l;j<=mid;j++) if(d[j]==-1) s[j]=1;
            int resp2=query(s),L=l;

            //cout<<resp<<"::"<<resp2<<endl;

            if((resp==i and resp2==i) or (resp>i and resp2>i))
            {
                l=mid+1;
                ans=mid+1;
            }
            else
            {
                r=mid;
                ans=mid;
            }

            for(int j=L;j<=mid;j++) if(d[j]==-1) s[j]=0;
        }

        //cout<<i<<"->"<<ans<<endl;
        d[ans]=i;
        if(resp==i) s[ans]=1;
    }

    answer(s,d);
}

/*
int main()
{
    read();
    exploreCave(n);

    return 0;
}
*/

/*
4
1 1 1 0
3 1 0 2
*/

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