Submission #806998

#	Time	Username	Problem	Language	Result	Execution time	Memory
806998		kshitij_sodani	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1036 KiB

prison

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;

#include "prison.h"

//vector<int> ss={1000,333,111,37,12,5,3};
vector<int> ss={1250,416,138,46,22,10,4,2};


int apply(int i,int j,int k){
    i--;
    for(int ii=0;ii<=j;ii++){
        i=i%ss[ii];
        if(i==0){// or i==ss[ii]-1){
            if(k==0){
                return -1;
            }
            else{
                return -2;
            }
        }
        else if(i==ss[ii]-1){
            if(k==0){
                return -2;
            }
            else{
                return -1;
            }
        }
        i--;
    }
   /* if(j+1==ss.size()){
        return -1;
    }*/
    return i;
}
vector<vector<int>> devise_strategy(int n){
    
    vector<vector<int>> ans;

    vector<pair<pair<int,int>,int>> mm;
    mm.pb({{0,0},0});//index in ss,divison number,bag number
    int cur=5000;

    int pr=5000;
    int cot=1;
    vector<int> rr;
    for(int i=0;i<ss.size();i++){
        rr.pb(mm.size());
        for(int j=0;j<((pr+ss[i]-1)/ss[i]);j++){
            mm.pb({{i,j},cot});
        }
        cot=cot^1;
        pr=ss[i]-2;
    }
    //mm.pb({{mm.back().a.a,mm.back().a.b+1},mm.back().b});
   /* for(auto j:mm){
        cout<<j.a.a<<":"<<j.a.b<<":"<<j.b<<endl;
    }*/
    
   /* cout<<apply(6,5,0)<<":"<<endl;
    cout<<apply(6,4,0)<<":"<<endl;
    cout<<apply(7,5,0)<<":"<<endl;
    cout<<apply(7,4,0)<<":"<<endl;
*/    for(int i=0;i<=20;i++){
        vector<int> kk;
        for(int j=0;j<=n;j++){
          kk.pb(0);
        }
        ans.pb(kk);
        if(i==0){
            ans[i][0]=0;
            for(int j=1;j<=n;j++){
                ans[i][j]=((j-1)/ss[0])+1;
            }
        }
        else if(mm[i].a.a+1==ss.size()){
            ans[i][0]=mm[i].b;
            //cout<<i<<";;;"<<endl;
            for(int j=1;j<=n;j++){
                ans[i][j]=apply(j,mm[i].a.a-1,mm[i].b);
                if(ans[i][j]==-1 or ans[i][j]==-2){
                    continue;
                }
                if(ans[i][j]==0){
                    if(mm[i].b==0){
                        ans[i][j]=-1;
                    }
                    else{
                        ans[i][j]=-2;
                    }
                }
                else if(ans[i][j]==1){
                    if(mm[i].b==1){
                        ans[i][j]=-1;
                    }
                    else{
                        ans[i][j]=-2;
                    }
                }
               /* else{
                    if(i==21){
                        if(mm[i].b==1){
                            ans[i][j]=-1;
                        }
                        else{
                            ans[i][j]=-2;
                        }
                    }
                    else{
                        if(mm[i].b==0){
                            ans[i][j]=-1;
                        }
                        else{
                            ans[i][j]=-2;
                        }
                    }
                }*/
                /*if(ans[i][j]!=-1 and ans[i][j]!=-2){
                    cout<<11<<endl;
                    cout<<j<<",,"<<endl;
                }*/
            }
        }
        else{
            ans[i][0]=mm[i].b;
            for(int j=1;j<=n;j++){
                int x=apply(j,mm[i].a.a-1,mm[i].b);
                if(x==-1 or x==-2){
                    ans[i][j]=x;
                    continue;
                }
                int xx=x/ss[mm[i].a.a];
                if(xx<mm[i].a.b){
                    if(ans[i][0]==0){
                        ans[i][j]=-1;
                    }
                    else{
                        ans[i][j]=-2;
                    }
                }
                else if(xx>mm[i].a.b){
                    if(ans[i][0]==0){
                        ans[i][j]=-2;
                    }
                    else{
                        ans[i][j]=-1;
                    }
                }
                else{
                    x%=ss[mm[i].a.a];
                  /*  x=apply(j,mm[i].a.a,mm[i].b);
                    if(x==-1 or x==-2){
                        ans[i][j]=x;
                    }
                    else{
                        int yy=x/ss[mm[i].a.a+1];
                        ans[i][j]=rr[mm[i].a.a+1]+yy;
                    }
                    continue;*/
                    if(x==0){
                        if(ans[i][0]==0){
                            ans[i][j]=-1;
                        }
                        else{
                            ans[i][j]=-2;
                        }
                    }
                    else if(x==ss[mm[i].a.a]-1){
                        if(ans[i][0]==0){
                            ans[i][j]=-2;
                        }
                        else{
                            ans[i][j]=-1;
                        }
                    }
                    else{
                        x--;
                      /*  if(mm[i].a.a+2==ss.size()){
                            if((x%ss[mm[i].a.a+1])==0){
                                ans[i][j]=21;
                                continue;
                            }
                        }*/
                       // if(mm[i].a.a+2==ss.size()){
                           /* if(x==0){
                                if(mm[i].b==0){
                                    ans[i][j]=-1;
                                }
                                else{
                                    ans[i][j]=-2;
                                }
                                continue;
                            }
                            else if(x==ss[mm[i].a.a+1]-1){
                                if(mm[i].b==1){
                                    ans[i][j]=-1;
                                }
                                else{
                                    ans[i][j]=-2;
                                }
                                continue;
                            }*/
                        //}
                      /*      else{
                                int yy=x/ss[mm[i].a.a+1];
                                ans[i][j]=rr[mm[i].a.a+1]+yy;
                            }
                            continue;
                        }*/
                        int yy=x/ss[mm[i].a.a+1];
                        ans[i][j]=rr[mm[i].a.a+1]+yy;
                    }
                }
            }
        }
    }
   // cout<<ans[15][6]<<";;;"<<endl;
    return ans;


}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<ss.size();i++){
      |                 ~^~~~~~~~~~
prison.cpp:81:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         else if(mm[i].a.a+1==ss.size()){
prison.cpp:47:9: warning: unused variable 'cur' [-Wunused-variable]
   47 |     int cur=5000;
      |         ^~~

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