Submission #833043

#	Time	Username	Problem	Language	Result	Execution time	Memory
833043		Kaitokid	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	11 ms	1108 KiB

prison

    #include "prison.h"
    #include "bits/stdc++.h"
    using namespace std;
     
    const int M = 8;
     
    int p[M];
     
    int check(int x, int k) {
      k--;
      return ((x / p[k]) % 3); 
    }
     
    vector<vector<int>> devise_strategy(int N) {
      vector<vector<int>> ret(M * 3 + 1, vector<int>(N + 1));
      ret[0][0] = 1; 
      p[0] = 1;
      for (int i = 1; i < M; ++i) p[i] = p[i - 1] * 3;
      for (int i = 1; i <= N; ++i) {
        ret[0][i] = M + M * check(i, M);
      }
      for (int i = 1; i <= M * 3; ++i) {
        int bit = i - ((i - 1) / M * M); 
        int state = (i - 1) / M; 
        if (bit % 2) {//we have the state of A
          ret[i][0] = 1; 
          for (int j = 1; j <= N; ++j) {
            if (state < check(j, bit)) {
              ret[i][j] = -1;
            } else if (state > check(j, bit)) {
              ret[i][j] = -2; 
            } else {
              if (bit > 1) {
                ret[i][j] = bit - 1 + M * check(j, bit - 1);            
              }
            }
          }
        } else {
          ret[i][0] = 0;
          for (int j = 1; j <= N; ++j) {
            if (state < check(j, bit)) {
              ret[i][j] = -2;
            } else if (state > check(j, bit)) {
              ret[i][j] = -1; 
            } else {
              if (bit > 1) {
                ret[i][j] = bit - 1 + M * check(j, bit - 1);            
              }
            }
          }
        }
      }
      return ret; 
    }

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