Submission #1211186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211186		nerrrmin	Prisoner Challenge (IOI22_prison)	C++20	36.50 / 100	11 ms	1608 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
int n;
struct node
{
    int bit, on, was;
    node() {};
    node(int _bit, int _on, int _was)
    {
        bit = _bit;
        on = _on;
        was = _was;
    }
};
node decode(int val)
{
    node ans;
    int bucket = val / 3;
    ans.bit = bucket;
    int ost = val % 3;

    if(ost == 0)
    {
        ans.on = 0;
        ans.was = 0;
    }
    else
    {
        ans.on = 1;

    if(ost == 1)
        ans.was = 0;
    else ans.was = 1;
    }
    //cout << val << " " << ans.bit << " " << ans.on << " " << ans.was << endl;
    return ans;
}
int encode(int bit, int on, int was)
{
    int res = bit * 3 + on + was;
   // cout << bit << " " << on << " " << was << " -> " << res << endl;
    return res;
}
int get_real_bit(int bit, int value)
{
    int realbit = 12-bit;
    if(value & (1 << realbit))return 1;
    else return 0;
}
std::vector<std::vector<int>> devise_strategy(int N)
{
 //   cout << "here "<< endl;
    n = N;

    vector < vector < int > > ans;
    ans.resize(40);
    for (int i = 0; i < 40; ++ i)
        ans[i].resize(n+1);
    for (int i = 0; i < 39; ++ i)
    {
        node status = decode(i);
        ans[i][0] = status.on;
        if(status.on == 0)
        {
            for (int val = 1; val <= n; ++ val)
            {
               node nxt = node(status.bit, 1, get_real_bit(status.bit, val));
               int code_nxt = encode(nxt.bit, nxt.on, nxt.was);
                ans[i][val] = code_nxt;
            }
        }
        else
        {
            for (int val = 1; val <= n; ++ val)
            {
               node nxt = node(status.bit+1, 0, 0);
               int has = get_real_bit(status.bit, val);
               if(has != status.was)
               {
                   if(has == 0)ans[i][val] = -2;
                    else ans[i][val] = -1;
               }
                else
                {
                      int code_nxt = encode(nxt.bit, nxt.on, nxt.was);
                ans[i][val] = code_nxt;
                }

            }
        }
    }
   // cout << "ended " << endl;

    return ans;
}

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