Submission #1247899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247899		denislav	Cave (IOI13_cave)	C++20	0 / 100	1 ms	324 KiB

cave

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

const int MAX=5e3+11;

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

}

int s[MAX]; ///ans
int d[MAX]; ///ans
int S[MAX];
int S2[MAX];

void exploreCave(int N)
{
    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 i=l;i<=mid;i++) S2[i]^=1;
            int resp2=query(S2);
            if((resp==i and resp2==i) or (resp>i and resp2>i))
            {
                r=mid+1;
                ans=mid+1;
            }
            else
            {
                l=mid;
                ans=mid;
            }

            for(int i=l;i<=mid;i++) S2[i]^=1;
        }

        d[ans]=i;
        if(resp==i)
        {
            s[ans]=(S[ans]^1);
            S[ans]^=1;
            S2[ans]^=1;
        }
        else s[ans]=S[ans];
    }

    answer(s,d);
}

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