Submission #1212879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212879		nerrrmin	죄수들의 도전 (IOI22_prison)	C++20	0 / 100	0 ms	324 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
int n;
/// 0 a 1 b
/// 1 2 - A bit 0
/// 3 4 - B bit 1
/// 5 6 - A bit 2
/// 7 8 - B bit 3
/// 9 10 - A bit 4
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 - 1) / 2;
    ans.bit = bucket;
    if(val & 1)ans.was = 0;
    else ans.was = 1;
    if(ans.bit % 2 == 0)ans.on = 1;
    else ans.on = 0;
    return ans;
}
int encode(int bit, int on, int was)
{
    assert(bit < 13);
    int base = (bit * 2) + 1;
    if(was == 1)base ++;

    return base;
}
int get_real_bit(int bit, int value)
{
    //cout << 12 - bit + 1 << endl;
    assert(bit <= 12);
    int realbit = 12-bit;
  //  if(bit == 12)cout << realbit << endl;
    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(25);
    for (int i = 0; i <= 24; ++ i)
        ans[i].resize(n);
    // ako sme na 0
    ans[0][0] = 1;
    for(int val = 1; val <= n; ++ val)
    {
        int nxt = encode(0, 1, get_real_bit(0, val));
        ans[0][val] = nxt;
      //  cout << nxt << endl;
    }
    for (int i = 1; i <= 24; ++ i)
    {
        node status = decode(i);
      //  cout << "* "<< status.on << " " << endl;
        ans[i][0] = 1 - status.on;

        for (int val = 1; val <= n; ++ val)
        {

            int has = get_real_bit(status.bit, val);

            if(has != status.was)
            {
                if((has == 0 && ans[i][0] == 0) || (has == 1 && ans[i][0] == 1))ans[i][val] = -1;
                else ans[i][val] = -2;
            }
            else if(status.bit < 11)
            {
                node nxt = node(status.bit+1, ans[i][0], get_real_bit(status.bit+1, val));
                int code_nxt = encode(nxt.bit, nxt.on, nxt.was);
                ans[i][val] = code_nxt;
            }
            else
            {
                int has = get_real_bit(status.bit+1, val);
              //  cout << status.bit+1 << endl;
                if(has == 1)
                {
                    if(ans[i][0])ans[i][val] = -1;
                    else ans[i][val] = -2;
                }
                else
                {
                     if(ans[i][0])ans[i][val] = -2;
                    else ans[i][val] = -1;
                }
            }

            assert(ans[i][val] < 25);
    }
}

return ans;
}

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