Submission #627035

#	Time	Username	Problem	Language	Result	Execution time	Memory
627035		LeMur	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	16 ms	2260 KiB

prison

#include "prison.h"

#include <vector>
#include <iostream>

using namespace std;

const int N = 20005;

int l[N], r[N];
int depth[N], id[N];
vector <int> children[N];
vector < pair<int, int> > vertices[30];

vector < vector<int> > answ;
int it = 1;

int max_height = 0;

void rec(int v, int s, int e, int h) {
  max_height = max(max_height, h);
  ///
  depth[v] = h;
  l[v] = s;
  r[v] = e;
  ///
  int len = e - s + 1;
  if (len <= 2) return ;

  int rem = len % 3;

  int cur_start = s;
  for (int i = 1; i <= 3; i++) {
    int cur_len = len / 3;
    if (rem > 0) {
      cur_len++;
      --rem;
    }
    ++it;
    id[it] = 3 * ((id[v] + 2) / 3) + i;
    ///
    vertices[ id[it] ].push_back( make_pair(v, it) );
    ///
    children[v].push_back(it);
    rec(it, cur_start, cur_start + cur_len - 1, h + 1);
    cur_start += cur_len;
  }
}

vector < vector<int> > devise_strategy(int n) {
  id[1] = 0;
  rec(1, 1, n, 0);

  answ.resize(3 * max_height + 1);

  answ[0].resize(n + 1, 0);
  answ[0][0] = 0;
  if (n == 2) {
    answ[0][1] = -1;
    answ[0][2] = -2;
  } else {
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < (int)children[1].size(); j++) {
        int vertex = children[1][j];
        if (i >= l[vertex] && i <= r[vertex]) {
          answ[0][i] = id[vertex];
        }
      }
    }
  }

  for (int x = 1; x <= 3 * max_height; x++) {
    answ[x].resize(n + 1, 0);
    ///
    answ[x][0] = ((x + 2) / 3) % 2;
    ///
    for (int ii = 0; ii < (int)vertices[x].size(); ii++) {
      int parent = vertices[x][ii].first;
      int current = vertices[x][ii].second;
      for (int i = l[parent]; i <= r[parent]; i++) {
        if (i <= l[current]) {
          if (answ[x][0] == 0) {
            answ[x][i] = -1;
          } else {
            answ[x][i] = -2;
          }
        } else if (i >= r[current]) {
          if (answ[x][0] == 0) {
            answ[x][i] = -2;
          } else {
            answ[x][i] = -1;
          }
        } else {
          if ((int)children[current].size() == 3) {
            for (int j = 0; j < (int)children[current].size(); j++) {
              int vertex = children[current][j];
              if (i >= l[vertex] && i <= r[vertex]) {
                answ[x][i] = id[vertex];
              }
            }
          } else {
            if (i == l[current]) {
              if (answ[x][0] == 0) {
                answ[x][i] = -1;
              } else {
                answ[x][i] = -2;
              }
            } else {
              if (answ[x][0] == 0) {
                answ[x][i] = -2;
              } else {
                answ[x][i] = -1;
              }
            }
          }
        }
      }
    }
  }

  // for (int x = 0; x <= 3 * max_height; x++) {
  //   for (int j = 0; j <= n; j++) {
  //     cout << answ[x][j] << " ";
  //   }
  //   cout << endl;
  //   cout << endl;
  // }

  return answ;
}

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