Submission #1248014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248014		linusvdv	Prisoner Challenge (IOI22_prison)	C++20	0 / 100	0 ms	328 KiB

prison

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

int x = 21;
std::vector<std::vector<int>> ans;
int n;


void setans(int level, int idx, int val) {
  if (idx >= 0 && idx < n) ans[level][idx+1] = val;
}

void dfs(int l, int r, int level) {
  if (level % 2 == 0) // left side
    for (int i = l - (r-l) - 1; i < l; i++) {
      setans(level, i, -ans[level][0]-1);
    }
  if (level % 2 == 1) // right side
    for (int i = r+1; i <= r + (r - l)+1; i++) {
      setans(level, i, ans[level][0]-2);
    }

  setans(level, l, -ans[level][0]-1);
  setans(level, r, ans[level][0]-2);

  if (l+3 == r) {
    for (int i = l+1; i < r; i++) {
      setans(level, i, x);
    }
    setans(x, l+1, -ans[x][0]-1);
    setans(x, r-1, ans[x][0]-2);
    return;
  }

  int m = (l+r)/2;
  for (int i = l+1; i < r; i++) {
      setans(level, i, int((level+1)/2)*2 + 1 + (i > m));
  }
  dfs(l+1, m, int((level+1)/2)*2 +1);
  dfs(m+1, r-1, int((level+1)/2)*2 + 2);
}

std::vector<std::vector<int>> devise_strategy(int N) {
  n = N;
  ans.assign(x+1, std::vector<int>(N+1, 0));
  // side
  for (int level = 0; level <= x; level++)
    ans[level][0] = ((level+1)/2)%2;

  dfs(0, 6141, 0);
/*  for (auto a : ans) {
    for (auto b : a) std::cout << (b < 0 ? " " : "  ") << b;
    std::cout << "\n";
  }*/
  return ans;
}

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