제출 #1002224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002224		overwatch9	동굴 (IOI13_cave)	C++17	100 / 100	193 ms	640 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;
        int res = tryCombination(query);
        while (l < r) {
            int mid = (l + r) / 2;
            for (int j = 0; j <= mid; j++)
                query[need_to_find[j]] = 1;
            int res2 = tryCombination(query);
            for (int j = 0; j <= mid; j++)
                query[need_to_find[j]] = 0;
            if ((min(res, res2) == -1 && max(res, res2) <= i) || (min(res, res2) != -1 && min(res, res2) <= i && max(res, res2) > i)) {
                r = mid;
                correct_pos = mid;
                if (res2 > i || res2 == -1)
                    state = 1;
                else
                    state = 0;
            } else {
                l = mid + 1;
            }
        }
        if (state == 2) {
            query[need_to_find[l]] = 1;
            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);
}

컴파일 시 표준 에러 (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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24