Submission #678472

#	Time	Username	Problem	Language	Result	Execution time	Memory
678472		cig32	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	980 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 = 22;
  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>=1; 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);
          if(i == 1 && bit(k, 0) == 2) ans[j][k] = -1;
          else if(i == 1 && bit(k, 0) == 0) ans[j][k] = -2;
        }
      }
    }
  }
 
  // Hardcode 22
  ans[22][0] = 0;
  for(int i=1; i<=N; i++) {
    int bb = bit(i, 0);
    if(bb > 1) ans[22][i] = -2;
    else ans[22][i] = -1;
  }
 
  return ans;
}

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