Submission #626167

#	Time	Username	Problem	Language	Result	Execution time	Memory
626167		Hanksburger	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1496 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> L[25], R[25], l[25], r[25], nothing;
vector<vector<int> > ans;
vector<vector<int> > devise_strategy(int n)
{
    for (int i=0; i<=n; i++)
        nothing.push_back(0);
    for (int i=0; i<=20; i++)
        ans.push_back(nothing);
    l[0].push_back(1);
    r[0].push_back(5102);
    int cnt=0;
    for (int i=0; i<=20; i++)
    {
//        cout << "i=" << i << '\n';
        for (int j=0; j<l[i].size(); j++)
        {
            if (i<=15)
            {
                l[cnt+1].push_back(l[i][j]+1);
                r[cnt+1].push_back((l[i][j]*2+r[i][j])/3);
                l[cnt+2].push_back((l[i][j]*2+r[i][j])/3+1);
                r[cnt+2].push_back((l[i][j]+r[i][j]*2)/3);
                l[cnt+3].push_back((l[i][j]+r[i][j]*2)/3+1);
                r[cnt+3].push_back(r[i][j]-1);
            }
            else
            {
                l[cnt+1].push_back(l[i][j]+1);
                r[cnt+1].push_back((l[i][j]+r[i][j])/2);
                l[cnt+2].push_back((l[i][j]+r[i][j])/2+1);
                r[cnt+2].push_back(r[i][j]-1);
            }
        }
        if (i%3==1)
        {
            R[i].push_back(i+1);
            if (i!=19)
                R[i].push_back(i+2);
        }
        else if (i%3==2)
        {
            L[i].push_back(i-1);
            if (i!=20)
                R[i].push_back(i+1);
        }
        else
        {
            if (i)
            {
                L[i].push_back(i-2);
                L[i].push_back(i-1);
            }
            cnt+=3;
        }
    }
    cnt=0;
    for (int i=0; i<=20; i++)
    {
//        cout << "i=" << i << '\n';
        for (int j=0; j<l[i].size(); j++)
        {
            if (l[i][j]<=n)
                ans[i][l[i][j]]=-1-ans[i][0];
            if (r[i][j]<=n)
                ans[i][r[i][j]]=-2+ans[i][0];
            for (int k=l[i][j]+1; k<=min(n, r[i][j]-1); k++)
            {
                if (k<=n)
                {
                    if (i<=15)
                    {
                        if (k<=(l[i][j]*2+r[i][j])/3)
                            ans[i][k]=cnt+1;
                        else if (k<=(l[i][j]+r[i][j]*2)/3)
                            ans[i][k]=cnt+2;
                        else
                            ans[i][k]=cnt+3;
                    }
                    else
                    {
                        if (k<=(l[i][j]+r[i][j])/2)
                            ans[i][k]=cnt+1;
                        else
                            ans[i][k]=cnt+2;
                    }
                }
            }
        }
        if (i)
        {
            for (int z=0; z<L[i].size(); z++)
            {
                int u=L[i][z];
//                cout << "u=" << u << '\n';
                for (int j=0; j<l[u].size(); j++)
                {
                    if (!z && l[u][j]-1<=n)
                        ans[i][l[u][j]-1]=-1-ans[i][0];
                    for (int k=l[u][j]; k<=min(n, r[u][j]); k++)
                        ans[i][k]=-1-ans[i][0];
                }
            }
            if (L[i].empty())
            {
                for (int j=0; j<l[i].size(); j++)
                    if (l[i][j]-1<=n)
                        ans[i][l[i][j]-1]=-1-ans[i][0];
            }
            for (int z=0; z<R[i].size(); z++)
            {
                int u=R[i][z];
//                cout << "u=" << u << '\n';
                for (int j=0; j<l[u].size(); j++)
                {
                    if (z==R[i].size()-1 && r[u][j]+1<=n)
                        ans[i][r[u][j]+1]=-2+ans[i][0];
                    for (int k=l[u][j]; k<=min(n, r[u][j]); k++)
                        ans[i][k]=-2+ans[i][0];
                }
            }
            if (R[i].empty())
            {
                for (int j=0; j<l[i].size(); j++)
                    if (r[i][j]+1<=n)
                        ans[i][r[i][j]+1]=-2+ans[i][0];
            }
        }
        if (i%3==0)
        {
            ans[cnt+1][0]=ans[i][0]^1;
            ans[cnt+2][0]=ans[i][0]^1;
            if (i!=18)
                ans[cnt+3][0]=ans[i][0]^1;
            cnt+=3;
        }
    }
//    for (int i=0; i<=10; i++)
//    {
//        for (int j=0; j<=10; j++)
//            cout << ans[i][j] << ' ';
//        cout << '\n';
//    }
    return ans;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:18:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (int j=0; j<l[i].size(); j++)
      |                       ~^~~~~~~~~~~~
prison.cpp:63:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int j=0; j<l[i].size(); j++)
      |                       ~^~~~~~~~~~~~
prison.cpp:94:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for (int z=0; z<L[i].size(); z++)
      |                           ~^~~~~~~~~~~~
prison.cpp:98:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for (int j=0; j<l[u].size(); j++)
      |                               ~^~~~~~~~~~~~
prison.cpp:108:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 for (int j=0; j<l[i].size(); j++)
      |                               ~^~~~~~~~~~~~
prison.cpp:112:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for (int z=0; z<R[i].size(); z++)
      |                           ~^~~~~~~~~~~~
prison.cpp:116:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 for (int j=0; j<l[u].size(); j++)
      |                               ~^~~~~~~~~~~~
prison.cpp:118:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                     if (z==R[i].size()-1 && r[u][j]+1<=n)
      |                         ~^~~~~~~~~~~~~~~
prison.cpp:126:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |                 for (int j=0; j<l[i].size(); j++)
      |                               ~^~~~~~~~~~~~

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