Submission #629483

#	Time	Username	Problem	Language	Result	Execution time	Memory
629483		arnold518	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	16 ms	1108 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N;

vector<vector<int>> devise_strategy(int _N)
{
    int P=12;
    N=_N;
    vector<vector<int>> ans;
    
    vector<int> V(N+1);
    V[0]=0;
    for(int i=1; i<=N; i++)
    {
        if(i&(1<<P)) V[i]=2;
        else V[i]=1;
    }
    ans.push_back(V);

    int t=0;
    for(int i=P; i>=1; i--)
    {
        vector<int> V0(N+1), V1(N+1);
        t=!t;
        V0[0]=V1[0]=t;
        for(int j=1; j<=N; j++)
        {
            if(j&(1<<i))
            {
                V0[j]=-(!t)-1;
                if(j&(1<<(i-1)))
                {
                    if(i>1) V1[j]=ans.size()+3;
                    else V1[j]=-(!t)-1;
                }
                else
                {
                    if(i>1) V1[j]=ans.size()+2;
                    else V1[j]=-t-1;
                }
            }
            else
            {
                V1[j]=-t-1;
                if(j&(1<<(i-1)))
                {
                    if(i>1) V0[j]=ans.size()+3;
                    else V0[j]=-(!t)-1;
                }
                else
                {
                    if(i>1) V0[j]=ans.size()+2;
                    else V0[j]=-t-1;
                }
            }
        }
        ans.push_back(V0);
        ans.push_back(V1);
    }

    return ans;
}

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