Submission #831450

#	Time	Username	Problem	Language	Result	Execution time	Memory
831450		Kaitokid	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	65 ms	1464 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)
    {
        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<<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);
        return res;

    }


  /*  int main()
    {

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

    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<v[i].size();j++)cout<<v[i][j]<<" ";
        cout<<endl;
    }

        return 0;
    }
*/

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:45:35: warning: unused variable 'd' [-Wunused-variable]
   45 |                 int h=(i-2+j-1)/j,d=(i-2)/j,r=(i-2)%j;
      |                                   ^
prison.cpp:46:21: warning: unused variable 'g' [-Wunused-variable]
   46 |                 int g=j-r;
      |                     ^

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