Submission #589955

#	Time	Username	Problem	Language	Result	Execution time	Memory
589955		KrisjanisP	Cave (IOI13_cave)	C++14	100 / 100	706 ms	464 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void exploreCave(int N) {
    int S[N],D[N],RD[N],Q[N];
    // S - correct switch state
    // D - to which door is switch connected
    // RD - to which switch is door connected
    // Q - query array
    for(ll i=0;i<N;i++)
    {
        for(ll j=0;j<N;j++) Q[j]=0;
        for(ll j=0;j<i;j++)
            Q[RD[j]] = S[RD[j]];
        ll qr = tryCombination(Q);
        ll c; // correct position
        if(qr==i) c=1;
        else c=0;
        ll l=0,r=N-1;
        while(l!=r)
        {
            ll m = (l+r)/2;
            for(ll j=0;j<N;j++) Q[j]=1-c;
            for(ll j=l;j<=m;j++)
                Q[j] = c;
            for(ll j=0;j<i;j++)
                Q[RD[j]] = S[RD[j]];
            ll qr = tryCombination(Q);
            if(qr==i) l=m+1;
            else r=m;
        }
        S[l] = c;
        RD[i] = l;
        D[l] = i;
    }
    answer(S,D);
}

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