Submission #634068

#	Time	Username	Problem	Language	Result	Execution time	Memory
634068		Utaha	Prisoner Challenge (IOI22_prison)	C++17	38 / 100	20 ms	1600 KiB

prison

#include "prison.h"

#include <vector>
using namespace std;

std::vector<std::vector<int>> devise_strategy(int N) {
  // 13 bits in total to check
  // check A ith bit: 0~12
  // check B ith bit, knowing A's ith bit = 0: 13~25
  // check B ith bit, knowing A's ith bit = 1: 26~38
  
  const int m = 13;
  const int checkA = 0;
  const int checkB0 = m;
  const int checkB1 = m + m;
  
  vector<vector<int>> ans;
  for (int i = 0; i < m; i++) {
    vector<int> v;
    v.clear();
    v.push_back(0); // bag A
    for (int j = 0; j < N; j++) {
      if (j & (1 << (m - 1 - i))) {
        v.push_back(checkB1 + i);
      }
      else {
        v.push_back(checkB0 + i);
      }
    }
    ans.push_back(v);
  }
  //checkB0
  for (int i = 0; i < m; i++) {
    vector<int> v;
    v.clear();
    v.push_back(1); // bag B
    for (int j = 0; j < N; j++) {
      if (j & (1 << (m - 1 - i))) {
        v.push_back(-1); // report B > A
      }
      else {
        v.push_back(checkA + i + 1);
      }
    }

    ans.push_back(v);
  }
  //checkB1
  for (int i = 0; i < m; i++) {
    vector<int> v;
    v.clear();
    v.push_back(1); // bag B
    for (int j = 0; j < N; j++) {
      if (j & (1 << (m - 1 - i))) {
        v.push_back(checkA + i + 1);
      }
      else {
        v.push_back(-2); // report A > B
      }
    }

    ans.push_back(v);
  }
  return ans;
}

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