Submission #629624

#	Time	Username	Problem	Language	Result	Execution time	Memory
629624		abeker	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	12 ms	1160 KiB

prison

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

int get_bit(int x, int i) {
  return x >> i & 1;
}

int cmp(int a, int b) {
  if (a == b)
    return -1;
  return a > b;
}

vector <vector <int>> devise_strategy(int N) {
  int lg = 0;
  while (1 << lg + 1 <= N)
    lg++;
  vector <vector <int>> strat(2 * lg + 1, vector <int> (N + 1));
  for (int i = 0; i <= 2 * lg; i++) {
    int group = (i + 1) / 2;
    strat[i][0] = group % 2;
    for (int j = 1; j <= N; j++) {
      int tmp = cmp(get_bit(j, lg - group + 1), i % 2);
      if (tmp == -1 && group == lg)
        tmp = j % 2;
      if (tmp == -1)
        strat[i][j] = 2 * group + 2 - get_bit(j, lg - group);
      else
        strat[i][j] = -(tmp ^ strat[i][0]) - 1;
    }
  }
  return strat;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:17:18: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   17 |   while (1 << lg + 1 <= N)
      |               ~~~^~~

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