Submission #629583

#	Time	Username	Problem	Language	Result	Execution time	Memory
629583		LeMur	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	14 ms	2088 KiB

prison

#include "prison.h"

#include <set>
#include <vector>
#include <iostream>

using namespace std;

const int N = 20005;

int l[N], r[N];
int 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);
  ///
  l[v] = s;
  r[v] = e;
  ///
  int len = e - s + 1;
  if (len <= 2) return ;

  s++;
  e--;
  len -= 2;

  int div = (v == 1) ? 2 : 3;
  int rem = len % div;

  int cur_start = s;
  for (int i = 1; i <= div; i++) {
    int cur_len = len / div;
    if (rem > 0) {
      cur_len++;
      --rem;
    }
    ++it;
    if (v == 1) {
      id[it] = i;
    } else {
      id[it] = 3 * h + i - 1;
    }
    ///
    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);

  int mx = 21;
  answ.resize(mx + 1);

  answ[0].resize(n + 1, 0);
  answ[0][0] = 0;
  answ[0][1] = -1;
  answ[0][n] = -2;
  for (int i = 2; 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 <= mx; x++) {
    answ[x].resize(n + 1, 0);
    ///
    if (x > 2) {
      answ[x][0] = ((x + 3) / 3) % 2;
    } else {
      answ[x][0] = 1;
    }
    ///
    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() != 0) {
            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: 80 / 90