Submission #1210708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210708		qwusha	Prisoner Challenge (IOI22_prison)	C++20	38 / 100	12 ms	1608 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;

ll K = 5001;

vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> s(39, vector<int>(n + 1));
    for (int val = 0; val < 39; val++) {
        if (val % 3 == 0) {
            s[val][0] = 0;
            for (int x = 1; x <= n; x++) {
                int l = 1, r = K;
                int done = val / 3;
                for (int i = 0; i < done + 1; i++) {
                    int mid = (l + r) / 2;
                    if (i == done) {
                        if (x < mid) {
                            s[val][x] = 3 * done + 1;
                        } else {
                            s[val][x] = 3 * done + 2;
                        }
                    } else {
                        if (x < mid) {
                            r = mid;
                        } else {
                            l = mid;
                        }
                    }
                }
            }
        } else {
            s[val][0] = 1;
            for (int x = 1; x <= n; x++) {
                int l = 1, r = K;
                int done = val / 3;
                int typ = val % 3;
                s[val][x] = (done + 1) * 3 % 39;
                for (int i = 0; i < done + 1; i++) {
                    int mid = (l + r) / 2;
                    if (i == done) {
                        if (x < mid) {
                            if (typ == 2) {
                                s[val][x] = -2;
                            }
                        } else {
                            if (typ == 1) {
                                s[val][x] = -1;
                            }
                        }
                    } else {
                        if (x < mid) {
                            r = mid;
                        } else {
                            l = mid;
                        }
                    }
                }
            }

        }
    }
    return s;
}

/*
bool judge(int a, int b) {
    auto s = devise_strategy(K - 1);
    int cur = 0;
    set<int> st;
    while (cur >= 0) {
        if (st.find(cur) != st.end()) {
            cout << "CYCLING? NUMBER " << cur << " ON CASE " << a << ' ' << b << endl;
            exit(0);
        }
        st.insert(cur);
        int val = a;
        if (s[cur][0] == 1) {
            val = b;
        }
        cur = s[cur][val];
    }
    if (cur == -1) {
        return a < b;
    } else {
        return a > b;
    }
}


signed main() {

    auto s = devise_strategy(K - 1);
    for (int i = 0; i < 10000; i++) {
        int a = rnd() % (K - 1) + 1;
        int b = rnd() % (K - 1) + 1;
        while (a == b) {
            b = rnd() % (K - 1) + 1;
        }
        if (!judge(a, b)) {
            cout << "FAIL ON " << a << ' ' << b << endl;
            return 0;
        }
        if (i % 200 == 99) {
            cout << "SUCCESS" << endl;
        }
    }
    cout << "TOTAL SUCCESS" << endl;

}*/

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