oj.uz

Submission #834102

# Submission time Handle Problem Language Result Execution time Memory
834102 2023-08-22T10:47:45 Z vnm06 Prisoner Challenge (IOI22_prison) C++17
100 / 100
 12 ms 6260 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5004 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 3 ms 5096 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 2 ms 5008 KB Output is correct
8 Correct 3 ms 5008 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5004 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 8 ms 5520 KB Output is correct
5 Correct 11 ms 5964 KB Output is correct
6 Correct 12 ms 6260 KB Output is correct
7 Correct 12 ms 6192 KB Output is correct
8 Correct 2 ms 5004 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 6 ms 5460 KB Output is correct
12 Correct 10 ms 5972 KB Output is correct