Submission #626420

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

prison

#include<bits/stdc++.h>
//#include "prison.h"
#pragma GCC optimize ("O3")
using namespace std;
#define el "\n"
#define se " "
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
const ll INF=1e18,ch=1e18;
ll a,b,c,d,n,COST,t,last,ab,ba,n1,n2,fl1,fl2,o1,o2,flag,flag1,flag2,g,m,m1,m2,i,j,lr,f,k,l,r,y,o,p,mx=-ch,mx1=-ch,mx2=-ch,q,q1,q2,q3,q4,mn=ch,mn1=ch,mn2=ch,f1,f2,f3,pos,ans,sum,sz=1,MOD=1e9+7,zero=0,a1,b1,c1,val,sum1,cur,res,ans1,res1,kk,kkk,cnt,cnt1,fl;
vector < vector < int > > devise_strategy(int N)
{
    n=N;
    vector < vector < int > > v;
    ll x=24;
    ll Q=1;
    for(i=1;i<x/3;i++)
    {
        Q*=3;
    }
    v.resize(x+1,vector<int>(n+1));
    v[0][0]=0;
    for(j=1;j<=n;j++)
    {
        v[0][j]=1+j/Q;
    }
    t=1;
    for(i=1;i<=x;i+=3)
    {
        q=0;
        v[i+q][0]=t;
        for(j=1;j<=n;j++)
        {
            sum=j%(Q*3);sum/=Q;
            if(sum<q)
            {
                if (t==0) v[i+q][j]=-1;
                else v[i+q][j]=-2;
            }
            else if (sum>q)
            {
                if (t==0) v[i+q][j]=-2;
                else v[i+q][j]=-1;
            }
            else
            {
                if (i==x-2) continue;
                q2=i+3+((j%Q)/(Q/3));
                v[i+q][j]=q2;
            }
        }
        q=1;
        v[i+q][0]=t;
        for(j=1;j<=n;j++)
        {
            sum=j%(Q*3);sum/=Q;
            if(sum<q)
            {
                if (t==0) v[i+q][j]=-1;
                else v[i+q][j]=-2;
            }
            else if (sum>q)
            {
                if (t==0) v[i+q][j]=-2;
                else v[i+q][j]=-1;
            }
            else
            {
                if (i==x-2) continue;
                q2=i+3+((j%Q)/(Q/3));
                v[i+q][j]=q2;
            }
        }
        q=2;
        v[i+q][0]=t;
        for(j=1;j<=n;j++)
        {
            sum=j%(Q*3);sum/=Q;
            if(sum<q)
            {
                if (t==0) v[i+q][j]=-1;
                else v[i+q][j]=-2;
            }
            else if (sum>q)
            {
                if (t==0) v[i+q][j]=-2;
                else v[i+q][j]=-1;
            }
            else
            {
                if (i==x-2) continue;
                q2=i+3+((j%Q)/(Q/3));
                v[i+q][j]=q2;
            }
        }
        if (t==0) t=1;
        else t=0;
        Q/=3;
    }
    return v;
}
//
//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
//    cin>>n>>a>>b;
//    vector < vector < int > > v=devise_strategy(a,b);
//}

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