Submission #834102

#	Time	Username	Problem	Language	Result	Execution time	Memory
834102		vnm06	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	6260 KiB

prison

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

vector<int> gr[200000];
int spint[200000][2];

void fill_int(int le, int ri)
{
    int id=2;
    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;
        if(ri-le<=5)
        {
            int mid=(le+ri)/2;
            gr[i].push_back(id);
            spint[id][0]=le+1;
            spint[id][1]=mid;
            id++;
            gr[i].push_back(id);
            spint[id][0]=mid+1;
            spint[id][1]=ri-1;
            id++;
        }
        else
        {
            int m1=(2*le+ri)/3, m2=(le+2*ri)/3;
            gr[i].push_back(id);
            spint[id][0]=le+1;
            spint[id][1]=m1;
            id++;
            gr[i].push_back(id);
            spint[id][0]=m1+1;
            spint[id][1]=m2;
            id++;
            gr[i].push_back(id);
            spint[id][0]=m2+1;
            spint[id][1]=ri-1;
            id++;
        }
        //cout<<i<<" "<<le<<" "<<ri<<endl;
    }
}

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++)
    {
        int brp=(i+2)/3;
        if(brp%2==0)
        {
            //cout<<"A: ";
            ans[i].push_back(0);
            for(int brA=1; brA<=N; brA++)
            {
                //cout<<brA<<" ";
                bool fl=1;
                int pos=1;
                for(int j=0; j<brp-1; j++)
                {
                    if(gr[pos].size()<2) {fl=0; break;}
                    if(spint[gr[pos][0]][0]<=brA && brA<=spint[gr[pos][0]][1]) pos=gr[pos][0];
                    else if(spint[gr[pos][1]][0]<=brA && brA<=spint[gr[pos][1]][1]) pos=gr[pos][1];
                    else if(gr[pos].size()<3) {fl=0; break;}
                    else pos=gr[pos][2];
                }
                if(!fl)
                {
                    ans[i].push_back(0);
                    continue;
                }
                if(i%3==1)
                {
                    if(i && gr[pos].size()>=1)  pos=gr[pos][0];
                    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[gr[pos][0]][1]) ans[i].push_back(i+3);
                    else if(brA<=spint[gr[pos][1]][1]) ans[i].push_back(i+4);
                    else ans[i].push_back(i+5);
                }
                else if(i%3==2)
                {
                    if(i && gr[pos].size()>=2) pos=gr[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[gr[pos][0]][1]) ans[i].push_back(i+2);
                    else if(brA<=spint[gr[pos][1]][1]) ans[i].push_back(i+3);
                    else ans[i].push_back(i+4);
                }
                else
                {
                    if(i && gr[pos].size()>=3) pos=gr[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[gr[pos][0]][1]) ans[i].push_back(i+1);
                    else if(brA<=spint[gr[pos][1]][1]) ans[i].push_back(i+2);
                    else ans[i].push_back(i+3);
                }
            }
            //cout<<endl;
        }
        else
        {
            //cout<<"B: ";
            ans[i].push_back(1);
            for(int brB=1; brB<=N; brB++)
            {
                //cout<<brB<<" ";
                bool fl=1;
                int pos=1;
                for(int j=0; j<brp-1; j++)
                {
                    if(gr[pos].size()<2) {fl=0; break;}
                    if(spint[gr[pos][0]][0]<=brB && brB<=spint[gr[pos][0]][1]) pos=gr[pos][0];
                    else if(spint[gr[pos][1]][0]<=brB && brB<=spint[gr[pos][1]][1]) pos=gr[pos][1];
                    else if(gr[pos].size()<3) {fl=0; break;}
                    else pos=gr[pos][2];
                }
                if(!fl)
                {
                    ans[i].push_back(0);
                    continue;
                }
                if(i%3==1)
                {
                    if(i && gr[pos].size()>=1) pos=gr[pos][0];
                    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[gr[pos][0]][1]) ans[i].push_back(i+3);
                    else if(brB<=spint[gr[pos][1]][1]) ans[i].push_back(i+4);
                    else ans[i].push_back(i+5);
                }
                else if(i%3==2)
                {
                    if(i && gr[pos].size()>=2) pos=gr[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[gr[pos][0]][1]) ans[i].push_back(i+2);
                    else if(brB<=spint[gr[pos][1]][1]) ans[i].push_back(i+3);
                    else ans[i].push_back(i+4);
                }
                else
                {
                    if(i && gr[pos].size()>=3) pos=gr[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[gr[pos][0]][1]) ans[i].push_back(i+1);
                    else if(brB<=spint[gr[pos][1]][1]) ans[i].push_back(i+2);
                    else ans[i].push_back(i+3);
                }
            }
            //cout<<endl;
        }
    }
    return ans;
}

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