Submission #1324000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324000		sh_qaxxorov_571	Cave (IOI13_cave)	C++20	100 / 100	532 ms	496 KiB

cave

#include "cave.h"
#include <vector>
#include <algorithm>

void exploreCave(int N) {
    int S[N], D[N], current_S[N];
    int real_S[N], real_D[N]; // Yakuniy javoblar uchun
    bool found[N]; // Kalit ishlatilganini tekshirish uchun

    for (int i = 0; i < N; i++) {
        found[i] = false;
        real_D[i] = -1;
    }

    for (int i = 0; i < N; i++) {
        // i-chi eshikni ochadigan kalitni va uning holatini topamiz
        for (int j = 0; j < N; j++) {
            if (found[j]) current_S[j] = real_S[j];
            else current_S[j] = 0;
        }

        int res = tryCombination(current_S);
        int target_state;
        
        // Agar res == i bo'lsa, eshik yopiq (holat 1 bo'lishi kerak)
        // Agar res > i yoki res == -1 bo'lsa, eshik ochiq (holat 0 ekan)
        if (res == -1 || res > i) target_state = 0;
        else target_state = 1;

        // Ikkilik qidiruv orqali qaysi kalit ekanini topamiz
        int low = 0, high = N - 1, key_pos = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            for (int j = 0; j < N; j++) {
                if (found[j]) current_S[j] = real_S[j];
                else if (j >= low && j <= mid) current_S[j] = target_state;
                else current_S[j] = 1 - target_state;
            }

            int res2 = tryCombination(current_S);
            if (res2 == -1 || res2 > i) {
                key_pos = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        real_S[key_pos] = target_state;
        real_D[key_pos] = i;
        found[key_pos] = true;
    }

    answer(real_S, real_D);
}

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