Submission #637748

#	Time	Username	Problem	Language	Result	Execution time	Memory
637748		slime	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	15 ms	1152 KiB

prison

#include "prison.h"
#include "bits/stdc++.h"
using namespace std;

#include <vector>

std::vector<std::vector<int>> devise_strategy(int N);



int bit(int n, int b) {
  int p = 1;
  for(int i=0; i<b; i++) p *= 3;
  n %= (3 * p);
  return n / p;
}
std::vector<std::vector<int>> devise_strategy(int N) {

  int x = 24;
  vector<vector<int> > ans;
  // each array inside should hv length = N + 1
  ans.resize(x + 1);
  for(int i=0; i<=x; i++) ans[i].resize(N + 1);
  
  ans[0][0] = 0;
  for(int i=1; i<=N; i++) ans[0][i] = bit(i, 7) + 1;

  for(int i=7; i>=0; i--) {
    for(int j=(7-i) * 3 + 1; j<=(7-i) * 3 + 3; j++) {
      ans[j][0] = i % 2;
      int cc = j - (7-i) * 3 - 1;
      for(int k=1; k<=N; k++) {
        int bb = bit(k, i);
        if(bb > cc) ans[j][k] = (i % 2 ? -1 : -2);
        else if(bb < cc) ans[j][k] = (i % 2 ? -2 : -1);
        else ans[j][k] = min(x, (8-i) * 3 + bit(k, i-1) + 1);
      }
    }
  }

  return ans;
}

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