Submission #628415

#	Time	Username	Problem	Language	Result	Execution time	Memory
628415		600Mihnea	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	73 ms	1028 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

std::vector<std::vector<int>> devise_strategy(int n) {
  ///ios::sync_with_stdio(0); cin.tie(0);
  vector<int> dp(n + 1), par(n + 1, 0);
  for (int i = 0; i <= n; i++) {
    if (i <= 2) {
      dp[i] = 0;
      continue;
    }
    dp[i] = i;
    for (int j = 1; j <= (i - 2); j++) {
      dp[i] = min(dp[i], dp[j] + ((i - 2 + j - 1) / j));
      if (dp[j] + ((i - 2 + j - 1) / j) == dp[i]) {
        par[i] = j;
      }
    }
    assert(par[i]);
  }
  int x = dp[n];
  vector<int> dims;
  vector<vector<int>> what(x + 1, vector<int> (n + 1, 0));
  {
    int current = n;
    while (current >= 3) {
      dims.push_back(current);
      current = par[current];
    }
    dims.push_back(current);
    ///reverse(dims.begin(), dims.end());
  }
 /// cout << "dims = ";
  /**for (int i = 0; i + 1 < (int) dims.size(); i++) {
    cout << i << " ---> " << dims[i] << " " << par[dims[i]] << " " << ((dims[i] - 2 + dims[i + 1] - 1) / (dims[i + 1])) << "\n";
  }
  exit(0);**/

  {
    int sum_test = 0;
    for (int i = 0; i + 1 < (int) dims.size(); i++) {
      sum_test += ((dims[i] - 2 + dims[i + 1] - 1) / (dims[i + 1]));
    }
    assert(sum_test == x);
  }

  vector<int> position(x + 1, 0);
  map<int, int> child;

  int current = 0;
  position[current++] = 0;

  for (int i = 0; i + 1 < (int) dims.size(); i++) {
    int now_len = dims[i];
    int new_len = dims[i + 1];
    int times = ((now_len - 2) + (new_len - 1)) / (new_len);
    for (int j = 1; j <= times; j++) {
      position[current++] = i + 1;
    }
  }

  for (int i = 0; i <= x; i++) {
    ///cout << i << " : " << position[i] << "\n";
  }
  ///exit(0);



  function<void(int, int, int, int)> dfs = [&] (int state, int turn, int l, int r) {
    if (l > r) {
     /// return;
    }
    what[state][0] = turn;
   /// cout << "label = " << state << ", ch = " << (char) (turn + 'A') << ", l = " << l << ", r = " << r << "\n";
  /**  if (turn == 1) {
      for (int j = 1; j <= n; j++) {
        if (j < l) {
          what[state][j] = -2;
        }
        if (j > r) {
          what[state][j] = -1;
        }
      }
    } else {
      for (int j = 1; j <= n; j++) {
        if (j < l) {
          what[state][j] = -1;
        }
        if (j > r) {
          what[state][j] = -2;
        }
      }
    }**/

    if (!(l + 1 <= r)) {
      return;
    }

    ///cout << state << " " << turn << " : " << l << " " << r << "\n";
    assert(l + 1 <= r);
    assert(turn == 0 || turn == 1);
    assert(0 <= state && state <= x);
    assert(0 <= position[state] && position[state] <= (int) dims.size());
    assert(r - l + 1 <= dims[position[state]]);

    if (turn == 0) {
      what[state][l] = -1;
      what[state][r] = -2;
    } else {
      what[state][l] = -2;
      what[state][r] = -1;
    }
    if (l + 1 <= r - 1) {
      int st = l + 1, dr = r - 1;
      assert(position[state] + 1 < (int) dims.size());

      int last = state;
      while (last + 1 < (int) position.size() && position[last + 1] == position[last]) {
        last++;
      }

      int now_len = dims[position[state]];
      int new_len = dims[position[state] + 1];
      int times = ((now_len - 2) + (new_len - 1)) / (new_len);

      vector<vector<int>> guys;
      vector<int> states;

      for (int iter = 1; iter <= times; iter++) {
        int l2 = st, r2 = min(dr, st + new_len - 1);

        assert(position[last + iter] == position[state] + 1);

        guys.push_back({});
        states.push_back(last + iter);

        for (int num = l2; num <= r2; num++) {
          what[state][num] = last + iter;
          guys.back().push_back(num);
        }

        dfs(last + iter, turn ^ 1, l2, r2);

        st = r2 + 1;
      }

      for (int i0 = 0; i0 < (int) guys.size(); i0++) {
        ///cout << " = " << states[i0] << "\n";
        if (turn == 1) {
          what[states[i0]][l] = -1;
          what[states[i0]][r] = -2;
        } else {
          what[states[i0]][l] = -2;
          what[states[i0]][r] = -1;
        }
        ///what[states[i0]][l] = (turn ^ 1);
        ///what[states[i0]][r] = (turn ^ 1 ^ 1);
        ///what[states[i0]][l] ^= 1, what[states[i0]][r] ^= 1;
        for (int i1 = 0; i1 < (int) guys.size(); i1++) {

          if (i0 == i1) continue;
          int who = (i0 < i1) ^ turn ^ 1;

          assert(who == 0 || who == 1);
          for (auto &yy : guys[i1]) {
            if (who == 0) {
              what[states[i0]][yy] = -1;
            } else {
              what[states[i0]][yy] = -2;
            }
          }

        }
      }
      assert(st == dr + 1);
    }
  };


  dfs(0, 0, 1, n);

  return what;
  for (int num = 0; num <= x; num++) {

  }

  assert(current == x + 1);
 /// cout << "\n";

 /// exit(0);

  for (int i = 0; i <= x; i++) {
 ///   cout << i << " : " << position[i] << "\n";
 ///   cout << i << " ---> " << sum[i] << " " << position[i] << "\n";
  }
  ///exit(0);

  /// la inceput ce fac? citesc A-ul
 /** int sum = 0;
  what[0][0] = 0;
  for (int val_a = 1; val_a <= n; val_a++) {
    if (val_a == 1) {
      what[0][val_a] = -1;
      continue;
    }
    if (val_a == n) {
      what[0][val_a] = -2;
      continue;
    }
    int j = dims[1];
    int delta_val_a = val_a - (2);
    int id = delta_val_a / j;
    what[0][val_a] = sum + 1 + id;

  }*/


  return what;
}

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