Submission #1234930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234930		mariza	Prisoner Challenge (IOI22_prison)	C++20	0 / 100	3 ms	580 KiB

prison

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

typedef long long ll;

ll nxt(ll w, ll x){
    if(w==0){
        ll a=x;
        if(a==1) return -1;
        else{
            ll ans;
            for(ll i=1; i<=12; i++){
                if((a&(1ll<<i))>0) ans=i;
            }
            return ans;
        }
    }

    else if(w<=12){
        ll b=x;
        ll ans=-1;
        for(ll i=0; i<=12; i++){
            if((b&(1ll<<i))>0) ans=i;
        }

        ll b1=-1, l=-1;
        for(ll i=0; i<=12; i++){
            if((b&(1ll<<i))>0) b1=l;
            else l=i;
        }
        
        if(ans==-1) return -1;
        else if(ans==w) return 19+((b1&(1ll<<3))>0);
        else if(ans<w) return -2;
        else return -1;
    }

    else if(w>=15){
        ll bit=(w-13)/2, y=(w-13)%2;
        if(bit%2==1){
            ll a=-1, l=-1;
            for(ll i=0; i<=12; i++){
                if((x&(1ll<<i))>0) a=l;
                else l=i;
            }
            ll la=(a&(1ll<<bit)), lb=y;

            if(la>lb) return -2;
            else if(lb>la) return -1;
            else return 13+(bit-1)*2+(a&(1ll<<(bit-1))>0);
        }
        else{
            ll b=-1, l=-1;
            for(ll i=0; i<=12; i++){
                if((x&(1ll<<i))>0) b=l;
                else l=i;
            }
            ll lb=(b&(1ll<<bit)), la=y;

            if(la>lb) return -2;
            else if(lb>la) return -1;
            else return 13+(bit-1)*2+(b&(1ll<<(bit-1))>0);
        }
    }

    else{
        ll bit=0, y=(w-13)%2;
        ll b=-1, l=-1;
        for(ll i=0; i<=12; i++){
            if((x&(1ll<<i))>0) b=l;
            else l=i;
        }
        ll lb=b%2, la=y;
        if(la>lb) return -2;
        else return -1;
    }
}

vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> ans(21,vector<int>(n+1,0));

    ans[0][0]=0;
    for(ll i=1; i<=12; i++) ans[i][0]=1;
    ans[13][0]=1;
    ans[14][0]=1;
    ans[15][0]=0;
    ans[16][0]=0;
    ans[17][0]=1;
    ans[18][0]=1;
    ans[19][0]=0;
    ans[20][0]=0;

    for(ll w=0; w<=20; w++){
        for(ll x=1; x<=n; x++){
            ans[w][x]=nxt(w,x);
            // cout<<ans[w][x]<<" ";
        }
        // cout<<endl;
    }

    return ans;
}

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