Submission #650444

#	Time	Username	Problem	Language	Result	Execution time	Memory
650444		berr	Prisoner Challenge (IOI22_prison)	C++17	72 / 100	15 ms	1108 KiB

prison

#include "prison.h"

#include <cassert>
#include <cstdio>

#include <string>
#include <vector>


#include <bits/stdc++.h>
using namespace std;

static constexpr int kNumPrisoners = 500;

static void invalid_strategy(std::string message) {
  printf("%s\n", message.c_str());
  exit(0);
}
std::vector<std::vector<int>> devise_strategy(int N)
{

    vector<vector<int>> s(24, vector<int> (N+1));

    /*
    0 ==> 23, 22      A
    23,22 ==> 21, 20  B
    21, 20 ==> 20, 19 A
    ..
    5 4 ==> (3, 2, 1) A
    3 2 1 =B*/

    for(int i=0; i<=23; i++)
    {
        if((i/2)%2==0) s[i][0]=0;
        else s[i][0]=1;
    }

    s[1][0]=1;

    for(int i=1; i<=N; i++)
    {
        if(i&(1<<12)) s[0][i]=2*11+1;
        else s[0][i]=2*11; 
    }

    for(int i=23; i>=6; i--)
    {
        for(int l=1; l<=N; l++)
        {
            if(l&(1<<((i/2)+1)))
            {
                if(i%2==0)                                                             
                {
                    if((i/2)%2==1) s[i][l]=-2;
                    else s[i][l]=-1;
                }
                else if(l&(1<<(i/2)))
                {
                    s[i][l]=2*(i/2-1)+1;
                }
                else
                {
                    s[i][l]=2*(i/2-1);
                }
            }
            else
            {
                if(i%2==1) 
                {
                    if((i/2)%2==1) s[i][l]=-1;
                    else s[i][l]=-2;
                }
                else if(l&(1<<(i/2)))
                {
                    s[i][l]=2*(i/2-1)+1;
                }
                else
                {
                    s[i][l]=2*(i/2-1);
                }
            } 
        }
    }

    //5
    for(int l=1; l<=N; l++)
    {

        int val=0;
        for(int i=0; i<3; i++)
        {
            if(l&(1<<i)) val+=(1<<i);
        }
        
        if(!(l&(1<<3)))
        {
            s[5][l]=-2;                   
        }
        else
        {
            if(val==7) s[5][l]=-1;
            else if(val>4) s[5][l]=3;
            else if(val>2) s[5][l]=2;
            else if(val==1) s[5][l]=1;
            else if(val==2) s[5][l]=1;
            else if(val==0) s[5][l]=-2;
        }
    }

    for(int l=1; l<=N; l++)
    {

        int val=0;
        for(int i=0; i<3; i++)
        {
            if(l&(1<<i)) val+=(1<<i);
        }
        
        if((l&(1<<3)))
        {
            s[4][l]=-1;                   
        }
        else
        {
            if(val==7) s[4][l]=-1;
            else if(val>4) s[4][l]=3;
            else if(val>2) s[4][l]=2;
            else if(val==1) s[4][l]=1;
            else if(val==2) s[4][l]=1;
            else if(val==0) s[4][l]=-2;
        }
    }


    for(int l=1; l<=N; l++)
    {
        int val=0;
        for(int i=0; i<3; i++)
        {
            if(l&(1<<i)) val+=(1<<i);
        }


        if(val>=6)
        {
            s[3][l]=-2;
            s[2][l]=-2;
            s[1][l]=-2;
        }
        else if(val>=4)
        {
      

            s[3][l]=-1;
            s[2][l]=-2;
            s[1][l]=-2;
        }
        else if(val>=2)
        {
            s[3][l]=-1;
            s[2][l]=-1;
            s[1][l]=-2;
        }

        else if(val>=1)
        {
            s[3][l]=-1;
            s[2][l]=-1;
            s[1][l]=-1;
        }
        else if(val>=0)
        {
            s[3][l]=-1;
            s[2][l]=-1;
            s[1][l]=-1;
        }
        
    }

    for(int i=0; i<=23; i++)
    {
        for(int l=0; l<=N; l++)
        {
            if(s[i][l]==-1) s[i][l]=-2;
            else if(s[i][l]==-2) s[i][l]=-1;
        }
    }
    return s;

}   

Compilation message (stderr)

prison.cpp:15:13: warning: 'void invalid_strategy(std::string)' defined but not used [-Wunused-function]
   15 | static void invalid_strategy(std::string message) {
      |             ^~~~~~~~~~~~~~~~

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