Submission #1075537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075537		mc061	Cave (IOI13_cave)	C++17	100 / 100	511 ms	956 KiB

cave

#pragma once

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

const int sz = 5000;
int ck[sz];
int idx_for[sz];
int ans[sz];
int st[sz];
int sta_for[sz];

int tryCombination(int S[]);
int tryC(const vector<int>& state, int cur_test, int switch_pos) {
    for (int i = 0; i < sz; ++i) ck[i] = switch_pos^1;
    for (int i = 0; i < cur_test; ++i) {
        ck[idx_for[i]] = sta_for[i];
    }
    for (int i = 0; i < state.size(); ++i) {
        ck[state[i]] = switch_pos;
    }
    return tryCombination(ck);
}
void answer(int S[], int D[]);

pair<int, int> solve(int idx, const vector<int>& candidates, int open_state) {
    if (candidates.size() == 1) return {candidates.front(), open_state};

    vector<int> left, right;
    for (int i = 0; i < candidates.size()/2; ++i) {
        left.push_back(candidates[i]);
    }
    for (int i = candidates.size()/2; i < candidates.size(); ++i) {
        right.push_back(candidates[i]);
    }
    int v = tryC(left, idx, open_state);
    if (v != idx) return solve(idx, left, open_state);
    return solve(idx, right, open_state);
}

//return switch responsible for door idx and state
pair<int, int> get_ans(int idx, vector<int> candidates) {
    int v = tryC(candidates, idx, 1);
    int open_state = 0;
    if (v != idx) open_state = 1;

    return solve(idx, candidates, open_state);
}

void exploreCave(int N) {
    vector<int> candidates;
    for (int i = 0; i < N; ++i) {
        candidates.push_back(i);
    }
    for (int i = 0; i < N; ++i) {
        auto [idx, state] = get_ans(i, candidates);
        // cerr << idx << "->" << i << "\n";
        idx_for[i] = idx;
        sta_for[i] = state;
        ans[idx_for[i]] = i;
        st[idx_for[i]] = state;
        candidates.erase(find(candidates.begin(), candidates.end(), idx));
    }

    // for (int i = 0; i < N; ++i) {
    //     cout << ans[i] << " ";
    // }
    // cout << "\n";
    // for (int i = 0; i < N; ++i) {
    //     cout << st[i] << " ";
    // }
    // cout << "\n";

    answer(st, ans);
}   

Compilation message (stderr)

cave.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
cave.cpp: In function 'int tryC(const std::vector<int>&, int, int)':
cave.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < state.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
cave.cpp: In function 'std::pair<int, int> solve(int, const std::vector<int>&, int)':
cave.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < candidates.size()/2; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
cave.cpp:34:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = candidates.size()/2; i < candidates.size(); ++i) {
      |                                       ~~^~~~~~~~~~~~~~~~~~~

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