제출 #1248017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248017		linusvdv	Prisoner Challenge (IOI22_prison)	C++20	90 / 100	7 ms	1604 KiB

prison

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

int x = 21;
//int x = 5;
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);
    }

  for (int cur = level; cur <= x; cur++) {
    setans(cur, l, -ans[cur][0]-1);
    setans(cur, r, ans[cur][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);
//  dfs(0, 21, 0);
/*  for (auto a : ans) {
    for (auto b : a) std::cout << (b < 0 ? "  " : (b >= 10 ? "  " : "   ")) << b;
    std::cout << "\n";
  }*/
  return ans;
}

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