Submission #1002109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002109		overwatch9	Cave (IOI13_cave)	C++17	0 / 100	134 ms	604 KiB

cave

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

void exploreCave(int N) {
    vector <int> need_to_find;
    for (int i = 0; i < N; i++)
        need_to_find.push_back(i);
    int s[N+1], d[N+1];
    int d_inv[N+1]; // the switch that controls door i
    for (int i = 0; i < N; i++) {
        int query[N+1];
        fill(query, query + N + 1, 0);
        for (int j = 0; j < i; j++) {
            query[d_inv[j]] = s[d_inv[j]];
        }
        // if (i == 1) {
        //     cout << "QUERY: ";
        //     for (int j = 0; j < N; j++)
        //         cout << query[j] << ' ';
        //     cout << '\n';
        // }
        int sz = need_to_find.size();
        // keep half of the positions of the remaining
        int l = 0, r = sz - 1;
        int correct_pos = 0;
        int state = 2;
        while (l < r) {
            int mid = (l + r) / 2;
            // if (i == 1) {
            //     cout << "QUERY: ";
            //     for (int j = 0; j < N; j++)
            //         cout << query[j] << ' ';
            //     cout << '\n';
            // }
            for (int j = 0; j <= mid; j++)
                query[need_to_find[j]] = 1;
            // if (i == 1) {
            //     cout << "QUERY: ";
            //     for (int j = 0; j < N; j++)
            //         cout << query[j] << ' ';
            //     cout << '\n';
            // }
            int res = tryCombination(query);
            for (int j = 0; j <= mid; j++)
                query[need_to_find[j]] = 0;
            int res2 = tryCombination(query);
            
            // if (i == 0) {
            //     cout << "RANGE: " << l << ' ' << r << '\n';
            //     cout << "RES: " << res << ' ' << res2 << ' ' << '\n';
            // }
            if (res != res2) {
                r = mid;
                correct_pos = mid;
                if (res > i || res == -1)
                    state = 1;
                else
                    state = 0;
            } else {
                l = mid + 1;
            }
        }
        if (state == 2) {
            query[need_to_find[l]] = 1;
            int res = tryCombination(query);
            if (res == -1 || res > i)
                state = 1;
            else
                state = 0;
        }
        // cout << i << ": " << l << " state: " << state << '\n';
        s[need_to_find[l]] = state;
        d[need_to_find[l]] = i;
        d_inv[i] = need_to_find[l];
        need_to_find.erase(need_to_find.begin() + l);
        // cout << "MODIFED: ";
        // for (auto j : need_to_find)
        //     cout << j << ' ';
        // cout << '\n';
    }
    answer(s, d);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:26:13: warning: variable 'correct_pos' set but not used [-Wunused-but-set-variable]
   26 |         int correct_pos = 0;
      |             ^~~~~~~~~~~

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