Submission #1216778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216778		giorgi123glm	Cave (IOI13_cave)	C++20	100 / 100	256 ms	536 KiB

cave

#include "cave.h"
#include <complex.h>
#include <iostream>
#include <mutex>
#include <vector>
using namespace std;

void exploreCave(int N) {
    vector <int> ans (N + 1);
    vector <int> ans1 (N + 1);
    vector <bool> locked (N + 1);

    for (int i = 0; i < N; i++) {
        int curres = tryCombination (ans.data());
        // cout << "-->" << i << ' ' << curres << '\n';
        if (curres == i) {
            // try to find correct one
            int L = 0, R = N - 1;
            int cans = 0;

            while (L <= R) {
                int mid = (L + R) / 2;

                vector <int> ask = ans;
                for (int i = 0; i <= mid; i++)
                    if (!locked[i])
                        ask[i] = 1;
                
                unsigned int getres = tryCombination (ask.data());
                // cout << mid << ' ' << getres << '\n';
                if (getres > i) {
                    R = mid - 1;
                    cans = mid;
                } else {
                    L = mid + 1;
                }
            }

            // cout << i << ' ' << cans << ' ' << 1 << '\n';

            ans[cans] = 1;
            ans1[cans] = i;
            locked[cans] = 1;
        } else {
            // try to find incorrect one
            int L = 0, R = N - 1;
            int cans = 0;

            while (L <= R) {
                int mid = (L + R) / 2;

                vector <int> ask = ans;
                for (int i = 0; i <= mid; i++)
                    if (!locked[i])
                        ask[i] = 1;
                
                unsigned int getres = tryCombination (ask.data());
                // cout << mid << ' ' << getres << '\n';
                if (getres == i) {
                    R = mid - 1;
                    cans = mid;
                } else {
                    L = mid + 1;
                }
            }

            // cout << i << ' ' << cans << ' ' << 0 << '\n';
            
            ans1[cans] = i;
            locked[cans] = 1;
        }
    }

    answer (ans.data(), ans1.data());
}

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