제출 #1308262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308262		afric	동굴 (IOI13_cave)	C++20	100 / 100	441 ms	544 KiB

cave

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

/*void answer(int i[5002], int j[5002])
{
    int N = 4;
    cout << "ANSWER with key Indexes = " << endl;
    for (int c = 0; c < N; c++)
    {
        cout << i[c] << " ";
    } 
    cout << endl << "key States = " << endl;
    for (int c= 0 ; c < N; c++)
    {
        cout << j[c] << " ";
    }
    cout << endl;
}

//TESTING
int tryCombination(int q[5002])
{
    vector<int> k_i = {1,0,1,0};
    vector<int> k_p = {2,3,0,1};
    int min = 6700; // 6 7 !
    int N = 4;
    for (int c= 0; c < N; c++)
    {
        cout << q[c] << " ";
        if (q[c]!=k_i[c]&&k_p[c]<min)
        {
            min = k_p[c];
        }
    }
    cout << "|";
    if (min==6700)
    {
        cout << "ANS = -1" << endl;
        return -1;
    }
    else{
        cout << "ANS = " << min << endl;
        return min;
    }
}*/

void binarySearch(int k, int n, int keyIndex[5002], int keyState[5002])
{
    // logN binary search to find key
    int ans[5002];
    for (int i = 0; i < n; i++)
    {
        if (keyState[i] == -1)
        {
            ans[i]=0;
        }
        else{
            ans[i] = keyState[i];
        }
    }

    int pos = 1;
    int a = tryCombination(ans);
    if (a>k || a==-1)
    {
        // correct position for switch is down
        pos = 0;
    }

    // binary search
    int start = 0;
    int end = n;
    while ((end-start)>1)
    {
        int mid = (start+end)/2;
        int q[5002];
        for (int i = 0; i < n; i++)
        {
            if (keyState[i]!=-1)
            {
                q[i]=keyState[i];
            }
            // first we query range(start..mid)
            else if (i >= start && i < mid)
            {
                // we want to query this i
                q[i] = pos;
            }
            else{
                // not in query --> use off position.
                q[i] = abs(pos-1);
            }
        }

        a = tryCombination(q);
        if (a > k || a==-1)
        {
            // first closed door after k so k must be open.
            end = mid;
        }
        else{
            start = mid;
        }
    }
    // binary search is over so start==end (covers 1)
    keyIndex[start] = k;
    keyState[start] = pos;
}

void exploreCave(int N)
{
    int keyIndex[5002];
    fill_n(keyIndex,5002,-1);
    int keyState[5002];
    fill_n(keyState,5002,-1);
    for (int i = 0; i < N; i++)
    {
        binarySearch(i,N,keyIndex,keyState);
    }
    answer(keyState,keyIndex);
}

/*// TESTING
int main()
{
    int N;
    cin >> N;
    exploreCave(N);
}*/

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