Submission #833790

#	Time	Username	Problem	Language	Result	Execution time	Memory
833790		vnm06	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	5 ms	980 KiB

prison

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

int spint[200000][2];

void fill_int(int le, int ri)
{
    spint[1][0]=le;
    spint[1][1]=ri;
    for(int i=1; i<20000; i++)
    {
        le=spint[i][0];
        ri=spint[i][1];
        if(ri-le<=1) continue;
        spint[2*i][0]=le+1;
        spint[2*i][1]=(le+ri)/2;
        spint[2*i+1][0]=(le+ri)/2+1;
        spint[2*i+1][1]=ri-1;
    }
}

vector<vector<int> > ans;

vector<vector<int> > devise_strategy(int N)
{
    fill_int(1, N);
    ans.resize(21);
    for(int i=0; i<=20; i++)
    {
        ///cout<<i<<endl;
        int brp=(i+1)/2;
        if(brp%2==0)
        {
            ans[i].push_back(0);
            for(int brA=1; brA<=N; brA++)
            {
                int pos=1;
                for(int j=0; j<brp-1; j++)
                {
                    if(spint[2*pos][0]<=brA && brA<=spint[2*pos][1]) pos*=2;
                    else pos=pos*2+1;
                }
                if(i%2)
                {
                    if(i) pos*=2;
                    if(brA<=spint[pos][0]) ans[i].push_back(-1);
                    else if(brA>=spint[pos][1]) ans[i].push_back(-2);
                    else if(brA<=(spint[pos][0]+spint[pos][1])/2) ans[i].push_back(i+2);
                    else ans[i].push_back(i+3);
                }
                else
                {
                    if(i) pos=2*pos+1;
                    if(brA<=spint[pos][0]) ans[i].push_back(-1);
                    else if(brA>=spint[pos][1]) ans[i].push_back(-2);
                    else if(brA<=(spint[pos][0]+spint[pos][1])/2) ans[i].push_back(i+1);
                    else ans[i].push_back(i+2);

                }
            }
        }
        else
        {
            ans[i].push_back(1);
            for(int brB=1; brB<=N; brB++)
            {
                int pos=1;
                for(int j=0; j<brp-1; j++)
                {
                    if(spint[2*pos][0]<=brB && brB<=spint[2*pos][1]) pos*=2;
                    else pos=pos*2+1;
                }
                if(i%2)
                {
                    pos*=2;
                    if(brB<=spint[pos][0]) ans[i].push_back(-2);
                    else if(brB>=spint[pos][1]) ans[i].push_back(-1);
                    else if(brB<=(spint[pos][0]+spint[pos][1])/2) ans[i].push_back(i+2);
                    else ans[i].push_back(i+3);
                }
                else
                {
                    pos=2*pos+1;
                    if(brB<=spint[pos][0]) ans[i].push_back(-2);
                    else if(brB>=spint[pos][1]) ans[i].push_back(-1);
                    else if(brB<=(spint[pos][0]+spint[pos][1])/2) ans[i].push_back(i+1);
                    else ans[i].push_back(i+2);

                }
            }
        }
    }
    return ans;
}

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