Submission #631743

#	Time	Username	Problem	Language	Result	Execution time	Memory
631743		Mahtimursu	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	17 ms	960 KiB

prison

#include "prison.h"

#include <vector>
#include <iostream>

using namespace std;

pair<int, int> split_range(int value, int a, int b) {
    // Remove endpoints
    a++;
    b--;

    int dif = b - a;
    dif /= 2;

    int c = a + dif;
    if (value <= c) return {a, c};
    return {c + 1, b};
}

pair<int, int> find_range(int value, int steps) {
    int a = 1;
    int b = 5000;

    while (steps--) {
        auto p = split_range(value, a, b);
        a = p.first;
        b = p.second;
    }
    return {a, b};
}

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/2 -> 1
    // 3/4 -> 2
    int steps = (i + 1) / 2;
    bool t = steps % 2;
    
    //cout << i << " j: " << j << " steps: " << steps << " turn: " << (t ? "B" : "A") << endl;

    if (j == 0) return t;

    auto r = find_range(j, steps);

    if (r.first >= j) {
        return ans(1, t);
    } else if (r.second <= j) {
        return ans(0, t);
    }

    auto nr = split_range(j, r.first, r.second);

    if (nr.first == r.first + 1) {
        return steps * 2 + 1;
    } else {
        return steps * 2 + 2;
    }
}

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

    int mx = 50;

    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);
    }

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

    return res;
}

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