제출 #1008443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008443		aParrot	죄수들의 도전 (IOI22_prison)	C++17	0 / 100	0 ms	356 KiB

prison

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

#define ll long long
#define vi vector<int>
#define pb push_back
#define coord pair<int, int>
const int MOD = 1e9 + 7;
const int MAXN = 1e3;
// int dp[MAXN];


vector<vector<int>> devise_strategy(int N) {
  // int len = ceil(log2(N));

  int m = 33;
  // int ans[32][5000];
  vector<vector<int>> ans(m, vector<int>(N+1, 0));

  // A = 0
  // B = 1
  for (int i=0; i<m; i++) {
    // first bit determines which bag to look at 
    int shouldInspect = i & 1;
    int nextBag = (shouldInspect+1)%2;
    ans[i][0] = shouldInspect;

    // which bit are we looking at?
    int place = 15 - (i >> 2);

    // was previous on or off?
    int prev = (i >> 1) & 1;

    for (int j=1; j<=N; j++) {
      // compare the bits at position place
      int bagBit = (j >> place) & 1;

      // draw is what the prisoner will draw on the board
      int draw = 0;
      draw |= nextBag<<0;  // set first bag bit

      // comparisons depend on if the current bag is A or B
      if (shouldInspect == 0) {
        // current bag=A, we cannot compare anything
        draw |= bagBit<<1;  // set the on/off bit
        draw |= (place<<2);  // set the place bit
      } else if (shouldInspect == 1) {
        // the current bag is B, we should compare
        if (prev == 1 && bagBit == 0) {
          // previous bag was larger
          if (shouldInspect == 0) {
            // if we now checked A, then B is lower
            draw = -2;
          } else {
            // if we now checked B, then A is lower
            draw = -1;
          }
        } else if (prev == 0 && bagBit == 1) {
          // current bag is larger
          if (shouldInspect == 0) {
            // if we now checked A, then A is lower
            draw = -1;
          } else {
            // if we now checked B, then B is lower
            draw = -2;
          }
        } else if (prev == bagBit) {
          // bag A and B have equal bits at place
          
          // move the bit to check right
          draw |= (place+1)<<2;
        }
      }

      ans[i][j] = draw;
    }
  }
  
  // print the ans
  // for (vector<int> ar : ans) {
  //   for (int x : ar) {
  //     cout << x << ", ";
  //   }
  //   cout << endl;
  // }
  
  return ans;
}

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