Submission #1212591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212591		vivkostov	Prisoner Challenge (IOI22_prison)	C++20	0 / 100	0 ms	328 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>otg;
vector<int>v;
int n,dp[5005],mas[10],group[30];
void make_dp()
{
    for(int i=3;i<=n;i++)
    {
        dp[i]=100000;
        for(int j=(i+1)/2;j<i;j++)
        {
            dp[i]=min(dp[i],dp[j]+2);
        }
        for(int j=(i+2)/3;j<i;j++)
        {
            dp[i]=min(dp[i],dp[j]+3);
        }
    }
}
void prec()
{
    mas[0]=5001;
    mas[1]=1944;
    mas[2]=648;
    mas[3]=216;
    mas[4]=72;
    mas[5]=24;
    mas[6]=8;
    mas[7]=8;
    mas[8]=4;
    mas[9]=2;
    for(int i=0;i<=22;i++)otg.push_back(v);
    otg[0].push_back(0);
    group[0]=1;
    for(int i=1;i<=18;i++)
    {
        otg[i].push_back(((i+2)/3)%2);
        group[i]=(i+5)/3;
    }
    otg[19].push_back(1);
    otg[20].push_back(1);
    otg[21].push_back(0);
    otg[22].push_back(0);
    group[19]=8;
    group[20]=8;
    group[21]=9;
    group[22]=9;
}
void fil(int ind)
{
    int gr=group[ind],gran=mas[gr],st,prev=mas[gr-1],cur,bag=otg[ind][0]+1;
    for(int i=1;i<=n;i++)
    {
        if(ind)
        {
            if(ind<=18)st=(ind-1)%3;
            else st=(ind-1)%2;
            cur=(i%mas[gr-2])/prev;
            if(st>cur)
            {
                otg[ind].push_back(-bag);
                continue;
            }
            if(st<cur)
            {
                otg[ind].push_back(-(bag%2+1));
                continue;
            }
            if(ind==21||ind==22)
            {
                cur=i%prev+1;
                cur=cur/2;
                if(!cur)otg[ind].push_back(-bag);
                else otg[ind].push_back(-(bag%2+1));
                continue;
            }
        }
        cur=i%prev;
        cur=cur/gran;
        if(ind<=18)otg[ind].push_back(((ind+2)/3)*3+cur+1);
        else otg[ind].push_back(((ind+1)/2)*2+cur+1);
    }
}
vector<vector<int>> devise_strategy(int N)
{
    n=N;
    prec();
    for(int i=0;i<=22;i++)
    {
        fil(i);
    }
    for(int i=0;i<=22;i++)
    {
        //cout<<i<<" | ";
        for(int j=0;j<=n;j++)
        {
            //cout<<otg[i][j]<<" ";
        }
        //cout<<endl;
    }
    //cout<<endl;
    //return otg;
    return otg;
}

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