Submission #719120

#	Time	Username	Problem	Language	Result	Execution time	Memory
719120		mathematik	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1408 KiB

prison

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

using namespace std;

vector<vector<int>> erg;

void fill2(int s, int e, int o, int d, bool bagB) {
  erg[o][0] = bagB;
  if (s >= e) return;

  int pickThis = -1 - bagB;
  int pickOther = -2 + bagB;

  erg[o][s] = pickThis;
  erg[o][e] = pickOther;

  for (int i = 1; i <= 2; i++)
  {
    erg[d * 3 + i][s] = pickOther;
    erg[d * 3 + i][e] = pickThis;
  }

  int t0 = s + 1;
  int t2 = e;
  int t1 = (t0 + t2) / 2;

  for (int i = t0; i < t1; i++)
  {
    erg[o][i] = 3 * d + 1;
  }
  erg[3 * d + 1][t0] = pickOther;
  erg[3 * d + 1][t1 - 1] = pickThis;
  for (int i = t1; i < t2; i++)
  {
    erg[3 * d + 1][i] = pickThis;
  }
  
  for (int i = t0; i < t1; i++)
  {
    erg[3 * d + 2][i] = pickOther;
  }
  for (int i = t1; i < t2; i++)
  {
    erg[o][i] = 3 * d + 2;
  }
  erg[3 * d + 2][t1] = pickOther;
  erg[3 * d + 2][t2 - 1] = pickThis;
}

void fill(int s, int e, int o, int d, bool bagB) {
  if (d == 6) {
    fill2(s, e, o, d, bagB);
    return;
  }

  erg[o][0] = bagB;
  if (s >= e) return;

  int pickThis = -1 - bagB;
  int pickOther = -2 + bagB;

  erg[o][s] = pickThis;
  erg[o][e] = pickOther;

  for (int i = 1; i <= 3; i++)
  {
    erg[d * 3 + i][s] = pickOther;
    erg[d * 3 + i][e] = pickThis;
  }
  

  int t0 = s + 1;
  int t3 = e;
  int t1 = (t0 + t0 + t3) / 3;
  int t2 = (t0 + t3 + t3) / 3;

  for (int i = t0; i < t1; i++)
  {
    erg[o][i] = d * 3 + 1;
  }
  for (int i = t1; i < t3; i++)
  {
    erg[d * 3 + 1][i] = pickThis;
  }
  
  for (int i = t0; i < t1; i++)
  {
    erg[d * 3 + 2][i] = pickOther;
  }
  for (int i = t1; i < t2; i++)
  {
    erg[o][i] = d * 3 + 2;
  }
  for (int i = t2; i < t3; i++)
  {
    erg[d * 3 + 2][i] = pickThis;
  }

  for (int i = t0; i < t2; i++)
  {
    erg[d * 3 + 3][i] = pickOther;
  }
  for (int i = t2; i < t3; i++)
  {
    erg[o][i] = d * 3 + 3;
  }

  fill(t0, t1 - 1, d * 3 + 1, d + 1, !bagB);
  fill(t1, t2 - 1, d * 3 + 2, d + 1, !bagB);
  fill(t2, t3 - 1, d * 3 + 3, d + 1, !bagB);
}

vector<vector<int>> devise_strategy(int N) {
  erg = vector<vector<int>>(21, vector<int>(N + 1));

  fill(1, N, 0, 0, true);
  
  return erg;
}

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