제출 #1351903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1351903		KALARRY	동굴 (IOI13_cave)	C++17	100 / 100	388 ms	572 KiB

cave

//chockolateman

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

using namespace std;

int n,query[5005],my_door[5005],my_status[5005];
bool avail[5005];

int ask_Query(vector<int> S)
{
    for(int i = 0 ; i < n ; i++)
        query[i] = S[i];
    return tryCombination(query);
}

void exploreCave(int N) 
{
    n = N;
    for(int i = 0 ; i < N ; i++)
        my_door[i] = -1;
    vector<int> S(N,0);
    for(int i = 0 ; i < N ; i++)
    {
        for(int j = 0 ; j < N ; j++)
        {
            avail[j] = false;
            if(my_door[j] != -1)
                S[j] = my_status[j];
            else
            {
                avail[j] = true;
                S[j] = 0;
            }
        }
        int res = ask_Query(S);
        if(res != i)
        {
            for(int j = 0 ; j < N ; j++)
                if(my_door[j]==-1)
                    S[j] = 1;
        }
        int K = N-i;
        while(K > 1)
        {
            int mid = K/2;
            int cnt = 0;
            for(int j = 0 ; cnt < mid && j < N ; j++)
                if(avail[j])
                {
                    S[j] ^= 1;
                    cnt++;
                }
            res = ask_Query(S);
            if(res == i)
            {
                K -= mid;
                cnt = 0;
                for(int j = 0 ; cnt < mid && j < N ; j++)
                    if(avail[j])
                    {
                        avail[j] = false;
                        cnt++;
                    }
            }
            else
            {
                K = mid;
                cnt = 0;
                for(int j = 0 ; j < N ; j++)
                {
                    if(avail[j])
                    {
                        cnt++;
                        if(cnt > mid)
                            avail[j] = false;
                        else
                            S[j] ^= 1;
                    }
                }
            }
        }
        for(int j = 0 ; j < N ; j++)
            if(avail[j])
            {
                my_door[j] = i;
                my_status[j] = S[j]^1;
            }
    }
    answer(my_status,my_door);
}

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