제출 #309364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309364		mihai145	동굴 (IOI13_cave)	C++14	100 / 100	996 ms	628 KiB

cave

#include "cave.h"

void exploreCave(int N) {
    int *correctPos = new int[N];
    int *door = new int[N];
    bool *stablePos = new bool[N];

    for(int i = 0; i < N; i++)
        {
            correctPos[i] = 0;
            door[i] = 0;
            stablePos[i] = 0;
        }

    int currentPosition = 0;

    for(int d = 0; d < N; d++)
        {
            int r = tryCombination(correctPos);
            if(r != d)
                {
                    currentPosition = 1 - currentPosition;

                    for(int i = 0; i < N; i++)
                        if(!stablePos[i])
                            correctPos[i] = 1 - correctPos[i];
                }

            ///pozitia corecta pentru a deschide usa d este 1 - currentPosition

            int *auxarr = new int[N];
            for(int i = 0; i < N; i++)
                auxarr[i] = 0;

            int st = 0, dr = N - 1;
            while(st < dr)
                {
                    int mid = (st + dr) >> 1;

                    for(int i = 0; i < N; i++)
                        if(stablePos[i]) auxarr[i] = correctPos[i];
                        else if(st <= i && i <= mid) auxarr[i] = 1 - currentPosition;
                        else auxarr[i] = currentPosition;

                    r = tryCombination(auxarr);

                    if(r != d)
                        {
                            ///pozitia corecta e in st...mid
                            dr = mid;
                        }
                    else
                        {
                            ///pozitia corecta e in mid+1...dr
                            st = mid + 1;
                        }
                }

            delete[] auxarr;

            stablePos[st] = 1;
            correctPos[st] = 1 - currentPosition;
            door[st] = d;
        }

    answer(correctPos, door);
    delete[] correctPos;
    delete[] door;
    delete[] stablePos;
}

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