제출 #634068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634068		Utaha	죄수들의 도전 (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