Submission #831467

#	Time	Username	Problem	Language	Result	Execution time	Memory
831467		Kaitokid	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	65 ms	1420 KiB

prison

        #include<bits/stdc++.h>
        using namespace std;
        typedef long long ll;
        vector<vector<int> > res;
        vector<int>op;
        vector<int>to;
        void go(int x,int l,int r,int ll,int rr,int u)
        {
            res[x][0]=u;
            for(int i=ll;i<=l;i++)res[x][i]=-u-1;
            for(int i=r;i<=rr;i++)res[x][i]=u-2;
            if(r<l+2)return;
            int len=r-l-1;
            int ln1=(len+op[len+2]-1)/op[len+2],ln2=len/op[len+2],cn1=len%op[len+2];
            int cn2=op[len+2]-cn1;
            int lst=to[x];
            int st=l+1;
            for(int i=0;i<cn1;i++)
            {
                for(int j=st;j<st+ln1;j++)res[x][j]=lst;
                go(lst,st,st+ln1-1,l,r,1-u);
                st+=ln1;
                lst++;
            }

            for(int i=0;i<cn2;i++)
            {
                for(int j=st;j<st+ln2;j++)res[x][j]=lst;
                go(lst,st,st+ln1-1,l,r,1-u);
                lst++;
                st+=ln2;
             }

        }
        vector<vector<int> > devise_strategy(int N)
        {
            int NN=N;
            N=5000;
            vector<int>dp(N+1),opt(N+1);
            dp[1]=0;
            dp[2]=0;
            for(int i=3;i<=N;i++)
            {
                dp[i]=1000000;
                for(int j=1;j<=i-2;j++)
                {
                    int h=(i-2+j-1)/j,d=(i-2)/j,r=(i-2)%j;
                    int g=j-r;
                    int res=j+dp[h];
                    if(res<dp[i]){dp[i]=res;opt[i]=j;}
                }
           //     cout<<i<<" "<<dp[i]<<endl;
            }
            //cout<<dp[N]<<endl;
            to.clear();
            vector<int>g;
            g.push_back(N);
            int num=1;
            while(!g.empty())
            {
              int h=to.size()+num;
              for(int i=0;i<num;i++)to.push_back(h);
              vector<int>gg;
              int f=0;
              for(auto u:g)
                    {   f=max(f,opt[u]);
                        if(opt[u]!=0)
                        {gg.push_back((u-2)/opt[u]);gg.push_back(((u-2)+opt[u]-1)/opt[u]);}}
                        g=gg;
                        num=f;
            }
         //   cout<<to.size()<<endl;
            res=vector<vector<int> >(to.size(),vector<int>(N+1));
            op=opt;
            go(0,1,N,1,N,0);
            for(int i=0;i<res.size();i++)
                while(res[i].size()>NN+1)res[i].pop_back();
            return res;

        }


        /*int main()
        {

        vector<vector<int> > v=devise_strategy(4993);
        cout<<v.size()<<endl;

        int hh=0;
        for(int i=0;i<v.size();i++)
        {
            for(int j=0;j<v[i].size();j++)hh=max(hh,v[i][j]);//cout<<v[i][j]<<" ";
          //  cout<<endl;
        }
       cout<<hh;
            return 0;
        }*/

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:47:39: warning: unused variable 'd' [-Wunused-variable]
   47 |                     int h=(i-2+j-1)/j,d=(i-2)/j,r=(i-2)%j;
      |                                       ^
prison.cpp:48:25: warning: unused variable 'g' [-Wunused-variable]
   48 |                     int g=j-r;
      |                         ^
prison.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(int i=0;i<res.size();i++)
      |                         ~^~~~~~~~~~~
prison.cpp:77:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |                 while(res[i].size()>NN+1)res[i].pop_back();
      |                       ~~~~~~~~~~~~~^~~~~

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