Submission #631805

#	Time	Username	Problem	Language	Result	Execution time	Memory
631805		Mahtimursu	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	1116 KiB

prison

#include "prison.h"

#include <vector>
#include <iostream>

using namespace std;

int get_bit(int val, int bit) {
    while (bit-- > 0) val /= 3;
    return val % 3;
}

int ans(bool low, bool t) {
    if (!low) t = !t;
    //         B    A
    return t ? -2 : -1;
}
 
int handle(int i, int j) {
    // 0 -> 0
    // 1-3 -> 1
    // 4-6 -> 2
    int steps = (i + 2) / 3;
    bool t = steps % 2;

    if (j == 0) return t;

    int cmp = i == 0 ? -1 : (i - 1) % 3;
    int bit = i == 0 ? -1 : get_bit(j, 8 - steps);
    
    if (i == 22) cmp = 1;

    if (cmp == -1) {
        return 1 + get_bit(j, 8 - steps - 1);
    } else if (bit < cmp) {
        return ans(1, t);
    } else if (bit > cmp) {
        return ans(0, t);
    } else {
        if (steps == 7) {
            int nxt_bit = get_bit(j, 0);
            if (nxt_bit == 0) return ans(1, t);
            else if (nxt_bit == 2) return ans(0, t);
            else return 22;
        }
        return steps * 3 + 1 + get_bit(j, 8 - steps - 1);
    }
}

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> res;

    int mx = 22;

    for (int i = 0; i <= mx; ++i) {
        vector<int> cur;
        for (int j = 0; j <= N; ++j) {
            cur.push_back(min(handle(i, j), mx));
        }
        res.push_back(cur);
    }

    /*int row = 0;
    for (auto g : res) {
        cout << row++ << ": ";
        for (int x : g) cout << x << " ";
        cout << endl;
    }*/

    return res;
}

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