Submission #1204569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204569		jer033	Cave (IOI13_cave)	C++20	In queue	0 ms	0 KiB

cave

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

int query(int N, int S[])
{
    int x = tryCombination(S);
    if (x==-1)
        return N;
    return x;
}

int flip_switches(int S[], int assignment[], int l, int r, int N)
{
    vector<int> changes;
    for (int i=l; i<=r; i++)
    {
        if (assignment[i] == -1)
        {
            changes.push_back(i);
            s[i] = 1;
        }
    }
    int ans = query(N, s);
    for (int i: changes)
        s[i] = 0;
    return ans;
}

void exploreCave(int N)
{
    int switches[N];
    int assignment[N];
    for (int i=0; i<N; i++)
    {
        switches[i] = 0;
        assignment[i] = -1;
    }
    for (int door = 0; door<N; door++)
    {
        int lo = 0;
        int hi = N-1;
        int curr = query(N, switches);
        while (lo!=hi)
        {
            int mid = (lo+hi)/2;
            if (flip_switches(switches, assignment, lo, mid, N) == curr)
                lo = mid+1;
            else
                hi = mid;
        }
        if (curr > door)
            switches[lo] = 0;
        else
            switches[lo] = 1;
        assignment[lo] = door;
    }
    answer(switches, assignment);
}