Submission #1192627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192627		hyakup	Prisoner Challenge (IOI22_prison)	C++20	38 / 100	11 ms	1608 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

const int maxk = 12;
const int maxb = 1;
const int maxc = 1;

using tripla = tuple<int, int, int>;

tripla decompose( int val ){
  if( val == 0 ) return tripla( maxk, 0, 0 );
  val--;
  if( val < maxk ) return tripla( val, 0, 0 );
  val -= (maxk);

  int b = val%2;
  val >>= 1;
  return tripla( val, b, 1 );
}

int compose( int k, int b, int c ){
  if( c == 0 ) return k + 1;
  return 2*k + b + maxk + 1;
}

vector<vector<int>> devise_strategy( int n ){
  int x = 3*maxk + 3;
  vector<vector<int>> resp( x, vector<int>(n + 1) );

  for( int i = 0; i < x; i++ ){
    auto [k, b, c] = decompose( i );
    resp[i][0] = c;
    if( c == 0 ) for( int j = 1; j <= n; j++ ) resp[i][j] = compose( k, (j>>k)&1, 1 );
    else for( int j = 1; j <= n; j++ ){
      int b2 = (j>>k)&1;
      if( b == b2 ) resp[i][j] = compose( max(k - 1, 0), 0, 0 );
      else if( b > b2 ) resp[i][j] = -2;
      else resp[i][j] = -1;
    }
  }


  return resp;
}

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