Submission #1224423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224423		trimkus	Prisoner Challenge (IOI22_prison)	C++20	56 / 100	8 ms	1348 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> devise_strategy(int N) {
    vector<vector<int>> res;
    vector<int> add(N + 1);
    int mxBit = 32 - __builtin_clz(N);
    // cout << mxBit << "\n";
    add[0] = mxBit & 1;
    add[1] = (add[0] ? -2 : -1);
    add[N] = (add[0] ? -1 : -2);
    for (int i = 2; i < N; ++i) {
      add[i] = 2 - (i >> (mxBit - 1) & 1);
    }
    res.push_back(add);
    for (int bit = mxBit - 1; bit >= 0; --bit) {
        int idx = (mxBit - bit) * 2 - 1;
        auto na = add;
        int turn = bit & 1;
        na[0] = turn;
        na[1] = (turn ? -2 : -1);
        na[N] = (turn ? -1 : -2);
        for (int i = 2; i < N; ++i) {
            if (i >> bit & 1) {
                if (bit == 0) {
                    na[i] = 0; // impossible?
                  continue;
                }
                int turnon = (i >> (bit - 1)) & 1;
                na[i] = idx + 3 - turnon;
            } else {
                na[i] = (turn ? -2 : -1);
            }
        }
        res.push_back(na);
        na = add;
        na[0] = turn;
        na[1] = (turn ? -2 : -1);
        na[N] = (turn ? -1 : -2);
        for (int i = 2; i < N; ++i) {
            if (!(i >> bit & 1)) {
                if (bit == 0) {
                    na[i] = 0; // impossible?
                  continue;
                }
                int turnon = (i >> (bit - 1)) & 1;
                na[i] = idx + 3 - turnon;
            } else {
                na[i] = (turn ? -1 : -2);
            }
        }
        res.push_back(na);
    }
    // for (auto& v : res) {
    //   for (auto& u : v) {
    //     cerr << u << " ";
    //   }
    //   cerr << "\n";
    // }
    // cerr << "\n";
    return res;
}

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