제출 #1308259

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

cave

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

/*void answer(vector<int> i, vector<int> j)
{
    cout << "ANSWER with key Indexes = " << endl;
    for (int item : i)
    {
        cout << item << " ";
    } 
    cout << endl << "key States = " << endl;
    for (int item : j)
    {
        cout << item << " ";
    }
    cout << endl;
}

//TESTING
int tryCombination(vector<int> q)
{
    for (int item : q)
    {
        cout << item << " ";
    }
    cout << endl;
    int a;
    cin >> a;
    return a;
}*/

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;
    if (tryCombination(ans)>k)
    {
        // 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);
            }
        }

        int a = tryCombination(q);
        if (a > k)
        {
            // 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: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24