Submission #1267145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267145		silentloop	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	7 ms	1096 KiB

prison

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define fr first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;

int con(ll x)
{
    if(x==1)
        return 2;
    return 1;
}

std::vector<std::vector<int>> devise_strategy(int N)
{
    ll i, j, ab=1, bit=7, sig=1, val, tam=23, aBit, aVal;

    vector<int>pot(9,1);
    for(i=1; i<=bit; i++)
        pot[i]=pot[i-1]*3;

    vector<vector<int>>ans(tam,vector<int>(N+1,0));
    for(i=1; i<tam; i+=3)
    {
        for(j=0; j<3; j++)
            if(i+j<tam)
                ans[i+j][0]=ab;
        ab=con(ab+1)-1;
    }

    for(i=1; i<=N; i++)
    {
        val=(i/pot[bit])%3;
        ans[0][i]=sig+val;
    }
    aBit=bit;
    bit--;
    sig+=3;
    for(j=1; j<tam-1; j++)
    {
        for(i=1; i<=N; i++)
        {
            val=(i/pot[aBit])%3;
            aVal=(j-1)%3;
            if(val<aVal)
                ans[j][i]=-(ans[j][0]+1);
            else if(val>aVal)
                ans[j][i]=-con(ans[j][0]+1);
            else
            {
                val=(i/pot[bit])%3;
                ans[j][i]=sig+val;
                if(ans[j][i]==24)
                    ans[j][i]=-1;
                if(ans[j][i]==22)
                    ans[j][i]=-2;
                if(ans[j][i]==23)
                    ans[j][i]=22;
            }
        }
        if(j%3==0)
        {
            aBit=bit;
            bit--;
            sig+=3;
        }
    }
    for(i=1; i<=N; i++)
    {
        val=i%3;
        aVal=1;
        if(val<=aVal)
            ans[22][i]=-(ans[22][0]+1);
        else
            ans[22][i]=-con(ans[22][0]+1);
    }
    /*for(i=0; i<sz(ans); i++)
    {
        for(j=0; j<sz(ans[i]); j++)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }*/
    return ans;
}

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