Submission #1204574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204574		jer033	Cave (IOI13_cave)	C++20	100 / 100	182 ms	540 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)>door)+(curr>door))%2)
                hi = mid;
            else
                lo = mid + 1;
        }
        if (curr > door)
            switches[lo] = 0;
        else
            switches[lo] = 1;
        assignment[lo] = door;
    }
    answer(switches, assignment);
}

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