제출 #486478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486478		status_coding	동굴 (IOI13_cave)	C++14	0 / 100	36 ms	408 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

bool isOpen(int id, int v[])
{
    int ans = tryCombination(v);

    if(ans == -1 || ans > id)
        return true;
    return false;
}

int findPoz(int id, int curCol, int st, int dr, int col[], int qV[])
{
    if(st == dr)
        return st;

    int mij=(st+dr)/2;

    for(int i=st;i<=mij;i++)
    {
        if(col[i] != -1)
            qV[i]=col[i];
        else
            qV[i]=curCol;
    }
    for(int i=mij+1;i<=dr;i++)
    {
        if(col[i] != -1)
            qV[i]=col[i];
        else
            qV[i]=1-curCol;
    }

    if(isOpen(id, qV))
        return findPoz(id, curCol, st, mij, col, qV);
    else
        return findPoz(id, curCol, mij+1, dr, col, qV);
}

void exploreCave(int n)
{
    int col[n];
    int id[n];
    int qV[n];

    for(int i=0;i<n;i++)
    {
        col[i]=-1;
        id[i]=-1;
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(col[i] != -1)
                qV[i]=col[i];
            else
                qV[i]=0;
        }

        int curCol = isOpen(i, qV) ? 0 : 1;
        int curPoz = findPoz(i, curCol, 0, n-1, col, qV);

        col[curPoz] = curCol;
        id[curPoz] = i;
    }

    answer(col, id);
}

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