Submission #1192581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192581		hyakup	Prisoner Challenge (IOI22_prison)	C++20	30 / 100	15 ms	2120 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--;
  int k, b, c;
  c = val%2;
  val >>= 1;
  b = val%2;
  val >>= 1;
  k = val;
  return tripla( k, b, c );
}

int compose( int k, int b, int c ){
  return 4*k + 2*b + c + 1;
}

vector<vector<int>> devise_strategy( int n ){
  int x = 4*maxk + 2*maxb + maxc + 1 + 1;
  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: 20 / 90