제출 #107183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107183		stefdasca	동굴 (IOI13_cave)	C++14	100 / 100	1258 ms	640 KiB

cave

/*
        IOI 13-Cave

    The 70.000 queries limit suggests us that we should find the switch for each node in O(log n) questions.
    At each step, we will firstly find out which is the state for switch corresponding to door i, and then
we will use binary search on the possible range of the answer

*/
#include "cave.h"
#include<bits/stdc++.h>
void exploreCave(int N)
{
    int S[N+2], D[N+2];
    memset(S, 0, sizeof(S));
    memset(D, 0, sizeof(D));
    int P[N+2], pus[N+2];
    memset(P, 0, sizeof(P));
    memset(pus, 0, sizeof(pus));
    for(int i = 0; i < N; ++i)
    {
        int st = 0;
        int dr = N-1;
        for(int j = 0; j < N; ++j)
            if(pus[j])
                P[j] = S[j];
            else
                P[j] = 1;
        int ans = tryCombination(P);
        bool ce = 0;
        if(ans > i || ans == -1)
            ce = 1;
        while(st < dr)
        {
            int mid = (st + dr) / 2;
            for(int j = 0; j < N; ++j)
            {
                if(pus[j])
                    P[j] = S[j];
                else
                    if(st <= j && j <= mid)
                        P[j] = ce;
                    else
                        P[j] = ce ^ 1;
            }
            ans = tryCombination(P);
            if(ans > i || ans == -1)
                dr = mid;
            else
                st = mid + 1;
        }
        pus[st] = 1;
        D[st] = i;
        S[st] = ce;
    }
    answer(S, D);
}

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