제출 #723403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723403		adrilen	동굴 (IOI13_cave)	C++17	100 / 100	800 ms	716 KiB

cave

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

using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
constexpr int maxn = 5e3 + 5;

int state[maxn] = { 0 }, pos[maxn] = { 0 }; // Pos gives the position of the ith switch, state gives the ith state
bool determined[maxn] = { 0 };

void exploreCave(int n) {
    int a, l, u, mid, nmid;
    int t;
    for (int i = 0; i < n; i++)
    {
        for (int y = 0; y < n; y++)
        {
            if (determined[y]) continue;
            state[y] = 0;
        }

        a = tryCombination(state);
        if (a == -1) a = n;

        if (a > i) {
            t = 0;
        } else {
            t = 1;
        }

        l = 0, u = n - 1;
        while (l != u)
        {

            nmid = (l + u + 1) >> 1;

            for (int y = 0; y < nmid; y++)
            {
                if (determined[y]) continue;
                state[y] = ((t + 1) & 1);
            }
            for (int y = nmid; y < n; y++)
            {
                if (determined[y]) continue;
                state[y] = t;
            }
            
            mid = nmid;
            a = tryCombination(state);


            if (a == -1) a = n;




            if (a > i) {
                l = mid;
            } else {
                u = mid - 1;
            }
        }

        pos[i] = l;
        determined[l] = true;
        state[l] = t;
    }
    
    int pos_output[maxn] = { 0 };
    

    for (int i = 0; i < n; i++)
    {
        pos_output[pos[i]] = i;
    }
    answer(state, pos_output);
}

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