Submission #855995

#	Time	Username	Problem	Language	Result	Execution time	Memory
855995		FilipL	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1372 KiB

prison

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define array_log(arr, x) {rep(y, x) {cout << arr[y] << ' ';} cout << '\n';}
#define unordered_map __gnu_pbds::gp_hash_table
using ll = long long;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;

#define LOCAL true

const int STATES = 21;
const int MAX_N = 5000;

struct Node {
    pii range;
    vector<Node> children;
    void expand(int depth) {
        int selfsize = range.second - range.first + 1;
        if (selfsize <= 2) return;
        int cur_s = range.first + 1;
        if (depth <= 6) {  // split into 3
            children = { Node{}, Node{}, Node{} };
            int childsize = (selfsize-2) / 3;
            int childsizemod = (selfsize-2) % 3;
            rep(i, 3) {
                if (childsizemod > 0) {
                    children[i].range = {cur_s, cur_s+childsize};
                    childsizemod--;
                } else children[i].range = {cur_s, cur_s+childsize-1};
                cur_s = children[i].range.second + 1;
                children[i].expand(depth+1);
            }
        } else {  // split into 2
            children = { Node{}, Node{} };
            int childsize = (selfsize-2) / 2;
            int childsizemod = (selfsize-2) % 2;
            if (childsizemod == 0) {
                children[0].range = {cur_s, cur_s+childsize-1};
                children[1].range = {cur_s+childsize, cur_s+childsize*2 - 1};
            } else {
                children[0].range = {cur_s, cur_s+childsize};
                children[1].range = {cur_s+childsize+1, cur_s+childsize*2};
            }
        }
    }
};
Node root;

const int LOWER_BOUND = -1337;
const int UPPER_BOUND = -4200;

vector<int> paths[MAX_N+7];
void calc_paths() {
    Node* nodeptr;
    rep1(val, MAX_N) {
        nodeptr = &root;
        while (true) {
            if (val == nodeptr->range.first) {
                paths[val].push_back(LOWER_BOUND);
                break;
            }
            if (val == nodeptr-> range.second) {
                paths[val].push_back(UPPER_BOUND);
                break;
            }
            rep(i, nodeptr->children.size()) {
                if (val <= nodeptr->children[i].range.second) {
                    paths[val].push_back(i);
                    nodeptr = &nodeptr->children[i];
                    break;
                }
            }
        }
    }
}

pii statetoboard[107];
map<pii, int> boardtostate;
void calc_trans() {
    int s = 1;
    rep1(depth, 6) {
        rep(path, 3) {
            pii board = {depth, path};
            statetoboard[s] = board;
            boardtostate[board] = s++;
        }
    }
    statetoboard[s] = {7, 0};
    boardtostate[{7, 0}] = s++;
    statetoboard[s] = {7, 1};
    boardtostate[{7, 1}] = s++;
}

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> strat = vector<vector<int>>(STATES, vector<int>(N+1, 0));

    root.range = {1, 5000};
    root.expand(1);
    calc_paths();
    calc_trans();

    // board == 00
    rep1(num, N) {
        if (paths[num][0] == LOWER_BOUND) strat[0][num] = -1;
        else if (paths[num][0] == UPPER_BOUND) strat[0][num] = -2;
        else strat[0][num] = boardtostate[{1, paths[num][0]}];
    }
    rep1(x, STATES-1) {
        pii board = statetoboard[x];
        int layer = board.first;
        int choice = board.second;
        int same = (layer % 2 == 0 ? -1 : -2);
        int other = (layer % 2 == 0 ? -2 : -1);
        strat[x][0] = -same - 1;
        rep1(num, N) {
            if (paths[num].size() < layer) continue;
            int numchoice = paths[num][layer-1];
            int nextchoice;
            if (paths[num].size() >= layer+1) nextchoice = paths[num][layer];
            if ((numchoice == LOWER_BOUND || numchoice < choice) && numchoice != UPPER_BOUND) strat[x][num] = same;
            else if ((numchoice == UPPER_BOUND || numchoice > choice) && numchoice != LOWER_BOUND) strat[x][num] = other;
            else if (nextchoice == LOWER_BOUND) strat[x][num] = same;
            else if (nextchoice == UPPER_BOUND) strat[x][num] = other;
            else strat[x][num] = boardtostate[{layer+1, nextchoice}];
        }
    }

    return strat;
}

Compilation message (stderr)

prison.cpp: In function 'void calc_paths()':
prison.cpp:4:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for (int a = 0; a < (b); a++)
      |                                     ^
prison.cpp:69:13: note: in expansion of macro 'rep'
   69 |             rep(i, nodeptr->children.size()) {
      |             ^~~
prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:119:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |             if (paths[num].size() < layer) continue;
      |                 ~~~~~~~~~~~~~~~~~~^~~~~~~
prison.cpp:122:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |             if (paths[num].size() >= layer+1) nextchoice = paths[num][layer];
      |                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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