Submission #918370

#	Time	Username	Problem	Language	Result	Execution time	Memory
918370		DobromirAngelov	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1372 KiB

prison

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

using namespace std;

vector<vector<int> > s;

int fewer(int bag)
{
    return -1-bag;
}

int child(int num,int ind)
{
    if(num>0)
    {
        if(num%3==0) num-=3;
        num=num+3-(num%3);
    }
    return num+ind;
}

void write(int num,int coins,int newNum)
{
    if(newNum>20) return;
    s[num][coins]=newNum;
}

void rec(int num,int bag,int l,int r,int parl,int parr)
{
    if(num>20) return;
    if(l>r) return;
    if(l>=r-1)
    {
        for(int i=parl;i<=parr;i++)
        {
            if(i<=l) write(num,i,fewer(bag));
            else if(r<=i) write(num,i,fewer(bag^1));
        }
        return;
    }

    int d=r-1-l;
    int len1,len2,len3;
    if(d<=4)
    {
        len1=len2=d/2;
        if(d%2>0) len1++;
    }
    else
    {
        len1=len2=len3=d/3;
        if(d%3>0) len1++;
        if(d%3>1) len2++;
    }
    int l1=l+1, r1=l1+len1-1, l2=r1+1, r2=l2+len2-1, l3=r2+1, r3=r-1;
    for(int i=parl;i<=parr;i++)
    {
        if(i<=l) write(num,i,fewer(bag));
        else if(r<=i) write(num,i,fewer(bag^1));
        else
        {
            if(l1<=i && i<=r1) write(num,i,child(num,1));
            else if(l2<=i && i<=r2) write(num,i,child(num,2));
            else if(l3<=i && i<=r3) write(num,i,child(num,3));
        }
    }

    rec(child(num,1),bag^1,l1,r1,l,r);
    rec(child(num,2),bag^1,l2,r2,l,r);
    rec(child(num,3),bag^1,l3,r3,l,r);
}

std::vector<std::vector<int>> devise_strategy(int n)
{
    s.resize(21, vector<int>(n+1,0));

    for(int i=0;i<=20;i++) s[i][0]=((i+2)/3)%2;
    rec(0,0,1,n,1,n);

    return s;
}

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