Submission #1105080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105080		fve5	Prisoner Challenge (IOI22_prison)	C++17	5 / 100	11 ms	11600 KiB

prison

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

struct Range { int l, r; };

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> ans;
    
    auto rec = [&](auto &&rec, bool fst, vector<Range> my_rng, vector<Range> o_rng) -> int {
        int sz = ans.size();
        ans.emplace_back(N + 1, -1);

        ans[sz][0] = fst;

        vector<Range> my_range_l, my_range_r;
        vector<int> rec_l, rec_r;

        for (int i = 0; i < my_rng.size(); i++) {
            auto [ml, mr] = my_rng[i];
            auto [ul, ur] = o_rng[i];

            for (int i = ml; i <= ul; i++)
                ans[sz][i] = fst ? -2 : -1;
            for (int i = ur - 1; i < mr; i++)
                ans[sz][i] = fst ? -1 : -2;

            if (ur - ul <= 2) continue;

            int m = (ul + ur) / 2;
            for (int i = ul + 1; i < m; i++)
                rec_l.push_back(i);
            for (int i = m; i < ur - 1; i++)
                rec_r.push_back(i);

            my_range_l.push_back({ul + 1, m});
            my_range_r.push_back({m, ur - 1});
        }

        if (!my_range_l.empty()) {
            int l = rec(rec, !fst, o_rng, my_range_l);
            int r = rec(rec, !fst, o_rng, my_range_r);

            for (auto x: rec_l)
                ans[sz][x] = l;
            for (auto x: rec_r)
                ans[sz][x] = r;
        }

        return sz;
    };

    rec(rec, true, {{1, N + 1}}, {{1, N + 1}});
    return ans;
}

Compilation message (stderr)

prison.cpp: In lambda function:
prison.cpp:19:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (int i = 0; i < my_rng.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
prison.cpp: In instantiation of 'devise_strategy(int)::<lambda(auto:23&&, bool, std::vector<Range>, std::vector<Range>)> [with auto:23 = devise_strategy(int)::<lambda(auto:23&&, bool, std::vector<Range>, std::vector<Range>)>&]':
prison.cpp:53:47:   required from here
prison.cpp:19:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 90