Submission #626993

#	Time	Username	Problem	Language	Result	Execution time	Memory
626993		cjoa	Prisoner Challenge (IOI22_prison)	C++17	42.50 / 100	17 ms	1500 KiB

prison

#include "prison.h"

#include <vector>
#include <map>
#include <iostream>
#include <cassert>

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using II = pair<int,int>;

enum Result {
   A_IS_SMALLER = -1, B_IS_SMALLER = -2
};

std::vector<std::vector<int>> devise_strategy(int N) {
   // map of (pos, digit) => x
   map<II,int> PD_to_x;
   vector<II> x_to_PD = { II(-1,-1) };
   // 0001 .. 4999 

   for (int pos = 0; pos <= 3; ++pos) {
      int upto = pos == 0 ? 4 : 9;
      for (int dig = 0; dig <= upto; ++dig) {
         II pd(pos, dig);
         int x = x_to_PD.size();
         x_to_PD.push_back(pd);
         PD_to_x[pd] = x;
      }
   }
   
   int M = int(x_to_PD.size())-1;
//   cerr << "max x = " << M << endl;

   int P10[] = {1, 10, 100, 1000};

   VVI ret(M + 1, VI(N + 1));
   ret[0][0] = 0;
   ret[0][1] = A_IS_SMALLER;
   ret[0][N] = B_IS_SMALLER;
   for (int n = 2; n < N; ++n) {
      int msd = n / P10[3];
      assert(PD_to_x.count(II(0, msd)));
      ret[0][n] = PD_to_x[II(0, msd)];
   }

   for (int x = 1; x <= M; ++x) {
      int pos, bdig;
      tie(pos, bdig) = x_to_PD[x];
      bool inspectA = pos % 2 == 1;
      ret[x][0] = inspectA ? 0 : 1;
      ret[x][1] = inspectA ? A_IS_SMALLER : B_IS_SMALLER;
      ret[x][N] = inspectA ? B_IS_SMALLER : A_IS_SMALLER;
      for (int n = 2; n < N; ++n) {
         int ndig = (n / P10[3-pos]) % 10;
         if (ndig < bdig) {
            ret[x][n] = inspectA ? A_IS_SMALLER : B_IS_SMALLER;
         }
         else if (ndig > bdig) {
            ret[x][n] = inspectA ? B_IS_SMALLER : A_IS_SMALLER;
         }
         else if (pos < 3) {
            ndig = (n / P10[3-(pos+1)]) % 10;
            assert(PD_to_x.count(II(pos+1, ndig)));
            ret[x][n] = PD_to_x[II(pos+1, ndig)];
         }
         else {
            ret[x][n] = -1;
         }
      }
   }

   /*
   for (int x = 0; x <= M; ++x) {
      int pos, dig;
      tie(pos, dig) = x_to_PD[x];
      if (x == 0 or x == 1 or x== 6 or x == 19 or x == 27) {
         cerr << x << " " << pos << "," << dig << ": ";
         for (int n = 0; n <= N; ++n)
            cerr << ret[x][n] << ' ';
         cerr << endl;
      }
   }
   */

   return ret;
}

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