Submission #675048

#	Time	Username	Problem	Language	Result	Execution time	Memory
675048		riverwalk3	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	14 ms	980 KiB

prison

#include "prison.h"
#include <iostream>
using namespace std;
int solve(int a, int b)
{
    const int MAXN = 5102;
    int l=1; int r = MAXN;
    int t = (((a+2)/3) % 2 ? 1: 0);
    for(int i=0; i<(a-1)/3; i++)
    {
        int t1 = (2*(l+1) + r)/3;
        int t2 = ((l+1) + 2*r)/3;
        if(l < b && b < t1)
        {
            l = l+1;
            r = t1-1;
        }
        else if(t1 <= b && b < t2)
        {
            l = t1; r = t2-1;
        }
        else if(t2 <= b && b < r)
        {
            l = t2; r = r-1;
        }
        else if(b == l)
        {
            return -1;
        }
        else if(b == r)
        {
            return -1;
        }
    }
    if(1 <= a && a <= 18)
    {
        int t1 = (2*(l+1) + r)/3;
        int t2 = ((l+1) + 2*r)/3;
        if(a % 3 == 1)
        {
            l = l+1; r = t1-1;
        }
        if(a % 3 == 2)
        {
            l = t1; r = t2-1;
        }
        if(a % 3 == 0)
        {
            l = t2; r = r-1;
        }
    }
    if(a == 19)
    {
        l = l+1; r = l+1;
    }
    if(a == 20)
    {
        l = l+3; r = l+1;
    }
    if(b <= l)
    {
        return -1-t;
    }
    if(b >= r)
    {
        return t-2;
    }
    int cur = (a+2)/3 * 3;
    if(a <= 15)
    {
        int t1 = (2*(l+1) + r)/3;
        int t2 = ((l+1) + 2*r)/3;
        if(l < b && b < t1)
        {
            return cur+1;
        }
        else if(t1 <= b && b < t2)
        {
            return cur+2;
        }
        else if(t2 <= b && b < r)
        {
            return cur+3;
        }
    }
    else
    {
        if(b <= l+2)
        {
            return cur+1;
        }
        else
        {
            return cur+2;
        }
    }
    return 0;
}
vector<vector<int> > devise_strategy(int N)
{
    const int x = 20;
    vector<vector<int> > strategy(x+1, vector<int>(N+1));
    for(int i=0; i<=x; i++)
    {
        strategy[i][0] = (((i+2)/3) % 2 ? 1: 0);
        for(int j=1; j<=N; j++)
        {
            strategy[i][j] = solve(i, j);
        }
    }
    return strategy;
}

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