Submission #627034

#	Time	Username	Problem	Language	Result	Execution time	Memory
627034		cjoa	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	16 ms	1012 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>;

#define SZ(x) (int((x).size()))

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) };

   const int K = 7;
   vector<int> P3 = {1};
   for (int k = 1; k <= K; ++k)
      P3.push_back(P3.back() * 3);
//   assert(P3.back() >= 5000);
//   cerr << P3.size() << ' ' << P3.back() << endl;

   for (int pos = K; pos > 0; --pos) {
      for (int dig = 0; dig <= 2; ++dig) {
         II pd(pos, dig);
         int x = x_to_PD.size();
         x_to_PD.push_back(pd);
         PD_to_x[pd] = x;
      }
   }
   // last digit has one choice
   int special_x;
   {
      II pd(0, 1);
      int x = x_to_PD.size();
      x_to_PD.push_back(pd);
      PD_to_x[pd] = x;
      special_x = x;
   }
   
   int M = int(x_to_PD.size())-1;
// cerr << "max x = " << M << endl;

   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 / P3[K];
      assert(PD_to_x.count(II(K, msd)));
      ret[0][n] = PD_to_x[II(K, msd)];
   }

   for (int x = 1; x <= M; ++x) {
      int pos, bdig;
      tie(pos, bdig) = x_to_PD[x];
      bool inspectA = (K-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 / P3[pos]) % 3;
         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 > 1) {
            ndig = (n / P3[pos-1]) % 3;
            assert(PD_to_x.count(II(pos-1, ndig)));
            ret[x][n] = PD_to_x[II(pos-1, ndig)];
         }
         else if (pos == 1) {
            ndig = (n / P3[pos-1]) % 3;
            switch (ndig) {
               case 0:
                  ret[x][n] = inspectA ? A_IS_SMALLER : B_IS_SMALLER;
                  break;
               case 2:
                  ret[x][n] = inspectA ? B_IS_SMALLER : A_IS_SMALLER;
                  break;
               case 1:
                  ret[x][n] = special_x;
                  break;
            }
         }
         else {
            ret[x][n] = -1;
         }
      }
   }

   /*
   for (int x = 0; x <= M; ++x) {
      int pos, dig;
      tie(pos, dig) = x_to_PD[x];
      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: 70 / 90