Submission #1092557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092557		TAMREF	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	8 ms	1176 KiB

prison

#include "prison.h"

#include <vector>
#include <tuple>
#include <utility>
#include <map>
#include <cassert>

using namespace std;
using pii = pair<int, int>;

const int P[10] = {1, 3, 9, 27, 81, 243, 729, 2187};

const int A_SMALL = -1;
const int B_SMALL = -2;

vector<vector<int>> devise_strategy(int N) {
  map<pii, int> M;
  M[pii(0, 1)] = 1;

  for(int i = 1; i <= 7; i++) {
    int x = M.size() + 1;
    M[pii(i, 0)] = x;
    M[pii(i, 1)] = x+1;
    M[pii(i, 2)] = x+2;
  }

  vector<vector<int>> ans(M.size() + 1, vector<int>(N + 1));
  
  ans[0][0] = 0;
  for(int i = 1; i <= N; i++) {
    ans[0][i] = M[pii(7, i / P[7])];
  }

  for(auto [k, i] : M) {
    auto [d, m] = k;

    ans[i][0] = (d & 1 ? 1 : 0);

    for(int c = 1; c <= N; c++) {
      if (d == 0) {
        ans[i][c] = (m == (c % P[1]) ? 0 : m < (c % P[1]) ? B_SMALL : A_SMALL);
        continue;
      }

      int me_m = (c / P[d]) % P[1];
      int me_small = (d & 1 ? B_SMALL : A_SMALL);
      int me_big = (d & 1 ? A_SMALL : B_SMALL);

      if (me_m == m) {
        int me_nxt = (c / P[d-1]) % P[1];
        if (d > 1) {
          ans[i][c] = M[pii(d-1, me_nxt)];
        } else {
          if (me_nxt == 1) {
            ans[i][c] = M[pii(d-1, me_nxt)];
          } else {
            ans[i][c] = (me_nxt == 2 ? me_big : me_small);
          }
        }
      } else {
        if (me_m < m) {
          ans[i][c] = me_small;
        } else {
          ans[i][c] = me_big;
        }
      }
    }
  }

  return ans;
}

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