Submission #1181373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181373		madamadam3	Prisoner Challenge (IOI22_prison)	C++20	5 / 100	4 ms	840 KiB

prison

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

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

int encode(bool checkB, int valueAtBit, int bitToCheck) {
  int ans = 0;
  ans |= ((checkB ? 1 : 0) << 6);
  ans |= (valueAtBit << 5);
  ans |= bitToCheck;

  return ans;
}

void decode(int encoded) {
  bool checkB = encoded & (1 << 6);
  int valueAt = (encoded & (1 << 5) ? 1 : 0);
  int curBit = encoded & ((1 << 4) - 1);

  cout << "We are checking the value of: " << (checkB ? "B" : "A") << "\n";
  cout << "Bit " << curBit << " of " << (checkB ? "A[i] ^ B[i] " : "A[i]") << "is " << valueAt << "\n";
}

vvi devise_strategy(int N) {
  int X = 128;
  vvi s(X+1, vi(N+1, 0));

  /*
    idea: prisoner by prisoner go through the bits of A and B
    state = [done 2] [a[i] ^ b[i]] [i] = 6 bits
  */
  
  for (int i = 0; i <= X; i++) {
    // if we are told to check A, then value of checkbit is A[i], and i is new
    int checkB = i & (1 << 6);
    int vat = (i & (1 << 5) ? 1 : 0);
    int curBit = 15 - (i & ((1 << 4) - 1)); 

    bool newCheckB = !checkB;
    int newCurBit = checkB ? (i & ((1 << 4) - 1)) + 1 : (i & ((1 << 4) - 1));
    s[i][0] = checkB ? 1 : 0;
    
    for (int j = 1; j <= N; j++) {
      int bitAt = (j & (1 << (15 - newCurBit))) ? 1 : 0;
      if (newCheckB) {
        if (bitAt != vat) {
          s[i][j] = bitAt == 1 ? -2 : -1;
        } else {
          s[i][j] = 0 | (newCheckB << 6) | (newCurBit) | ((bitAt ^ vat) << 5);
        }
      } else {
        s[i][j] = 0 | (newCheckB << 6) | (newCurBit) | (bitAt << 5);
      }
    }
  }

  for (int i = 0; i <= X; i++) {
    // cout << "i = " << i << ": [" << s[i][0];
    // for (int j = 1; j <= N; j++) {
    //   cout << ", " << s[i][j];
    // }
    // for (int j = 0; j <= N; j++) {
    //   if (!(-2 <= s[i][j] && s[i][j] <= X)) {
    //     cout << "s[" << i << "][" << j << "] is wrong!!\n";
    //   }
    // }
    // cout << "]\n";
  }
  return s;
}

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