Submission #630052

#	Time	Username	Problem	Language	Result	Execution time	Memory
630052		MojoLake	Prisoner Challenge (IOI22_prison)	C++17	30 / 100	40 ms	2352 KiB

prison

#include "prison.h"

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

int max_dig = 13;

bool get_first_bit(int num){
  return num%2;
}

bool get_second_bit(int num){
  return (num>>1)%2;
}

int get_pos(int num){
  return (num>>2);
}

int encode(int a, int on, int pos){
  return a + (on<<1) + (pos<<2);
}

std::vector<std::vector<int>> devise_strategy(int n) {
  
  int x = 60;
  vector<vector<int>> ret(x+1, vector<int> (n+1)); 
  max_dig = floor(log2(n));
  //cout << max_dig << "\n";
  //encode on which digit we are on
  //when at A:
  //take new one
  //encode
  //when at B:
  //take new one, check encoding
  //if different curbit -> return
  //if first digit 0: we are at A
  //else we are B:
  //next bit encodes whether the last bit
  //was on or off
  //next bit encodes the current bit
  for(int i = 0; i <= x; ++i){
    for(int j = 0; j <= n; ++j){
      
      if(j == 0){
          ret[i][j] = get_first_bit(i);
          continue;
      }


      if(get_first_bit(i) == 0){
        //A
        int cur_pos = i ? get_pos(i) : max_dig;
        bool cur_pos_on = j & (1<<cur_pos);

        ret[i][j] = min(x, encode(1, cur_pos_on, cur_pos));
      }

      else{
        //B
        bool cur_pos_on_in_a = get_second_bit(i);
        int cur_pos = get_pos(i);
        bool cur_pos_on = j & (1<<cur_pos);

        if(cur_pos_on != cur_pos_on_in_a){
          ret[i][j] = cur_pos_on ? -1 : -2;
        }
        else{
          if(cur_pos == 1){
            ret[i][j] = j & 1 ? -1 : -2;
          }
          else if(cur_pos == 0){
            ret[i][j] = -1;
          }
          else ret[i][j] = min(x, encode(0, 0, cur_pos - 1));
        }
      }

    }
  }

  ret[0][0] = 0;
  //2, 3
  //check a -> 2
  //ret = 1 + 2 + 4 = 7
  //
  //check b -> 3
  //cur_pos_on_in_a = 1
  //cur_pos = 1
  //cur_pos_on = 1
  //ret = 


  return ret;
}

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