Submission #666239

#	Time	Username	Problem	Language	Result	Execution time	Memory
666239		peijar	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	14 ms	1164 KiB

prison

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

vector<vector<int>> devise_strategy(int N) {
  int nbBits = max(10, (int)log2(N - 1) + 1);
  int B = nbBits - 1;
  int k = 2 * B + 1;
  cerr << k << endl;
  vector<vector<int>> strategy(k, vector<int>(N + 1));

  for (int i = 0; i < k; ++i) {
    if (i == 0) {
      strategy[i][0] = !((nbBits - 1) % 2);
      for (int j = 0; j < N; ++j) {
        if ((1 << (nbBits - 1)) & j)
          strategy[i][j + 1] = B + B;
        // strategy[i][j + 1] = nbBits + 1 + (nbBits - 1) - 2;
        else
          strategy[i][j + 1] = B;
        // strategy[i][j + 1] = 1 + (nbBits - 1) - 2;
      }
    } else {
      int bit = i <= B ? i : i - B;
      int big = i > B;
      strategy[i][0] = bit % 2;
      for (int j = 0; j < N; ++j) {
        if (big != !!((1 << bit) & j)) {
          if (big)
            strategy[i][j + 1] = -1 - bit % 2;
          else
            strategy[i][j + 1] = -2 + bit % 2;
        } else {
          if (bit == 1) {
            if (j % 2)
              strategy[i][j + 1] = -2 + bit % 2;
            else
              strategy[i][j + 1] = -1 - bit % 2;
          } else {
            assert(bit > 1);
            if ((1 << (bit - 1)) & j)
              strategy[i][j + 1] = B + bit - 1;
            else
              strategy[i][j + 1] = bit - 1;
          }
        }
      }
    }
  }
  return strategy;
}

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