Submission #1092940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092940		jerzyk	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1116 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 5000 + 7;
int pos[N];
vector<int> bas = {2, 3, 3, 3, 3, 2, 2, 2}, gs;

int Do(int n)
{
    int xd = 1, s = 1;
    gs.pb(1);
    for(int i = 0; i < (int)bas.size() && xd < n; ++i)
    {
        gs.pb(bas[i]);
        xd *= bas[i];
        //xd += 2;
        s += bas[i];
    }
    gs.pb(1);
    return s;
}

vector<vector<int>> devise_strategy(int _N)
{
    int n = _N, il;
    il = Do(n);
    for(int i = 1; i <= n; ++i) pos[i] = i - 1;
    pos[0] = -1; pos[n + 1] = -2;

    vector<int> bas(n + 1, -1);
    vector<vector<int>> ans(il, bas);
    int s = 0, r = 0, xd = n;

    for(int i = 1; i < (int)gs.size(); ++i)
    {
        //cerr << i << " " << gs[i] << "\n";
        for(int j = s; j <= s + gs[i - 1] - 1; ++j)
            ans[j][0] = r;
        //int d = (xd + (gs[i - 1] - 1)) / gs[i - 1];
        int d = xd;
        int nd = (xd - 2 + (gs[i] - 1)) / gs[i];
        for(int j = 1; j <= n; ++j)
        {
            //cerr << pos[j] << " ";
            if(pos[j] == -1)
                for(int l = 0; l < gs[i - 1]; ++l)
                    ans[s + l][j] = (-1 - r);
            if(pos[j] == -2)
                for(int l = 0; l < gs[i - 1]; ++l)
                    ans[s + l][j] = (-2 + r);
            if(pos[j] < 0) continue;

            int x = pos[j] / d;
            for(int l = 0; l < x; ++l)
                ans[s + l][j] = (-2 + r);
            for(int l = x + 1; l < gs[i - 1]; ++l)
                ans[s + l][j] = (-1 - r);

            if(pos[j] > 0) pos[j] %= d;
            if(pos[j] >= 0)
                --pos[j];
            if(pos[j] == d - 2 || pos[j + 1] < 0) pos[j] = -2;

            if(pos[j] == -1)
                ans[s + x][j] = (-1 - r);
            if(pos[j] == -2)
                ans[s + x][j] = (-2 + r);
            if(pos[j] >= 0)
                ans[s + x][j] = s + gs[i - 1] + (pos[j] / nd);
        }
        //cerr << "\n";
        s += gs[i - 1];
        r ^= 1;
        xd = (xd - 2 + gs[i] - 1) / gs[i];
    }
    /*cerr << ans.size() << "\n";
    for(int i = 0; i < (int)ans.size(); ++i)
    {
        for(int j = 0; j < (int)ans[i].size(); ++j)
            cerr << ans[i][j] << " ";
        cerr << "\n";
    }*/
    return ans;
}

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