Submission #626915

#	Time	Username	Problem	Language	Result	Execution time	Memory
626915		slime	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	13 ms	1188 KiB

prison

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

#include <vector>

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


std::vector<std::vector<int>> devise_strategy(int N) {
  int x = 26;
  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] = (i >= 4096 ? 2 : 1);
  }
  for(int i=1; i<=x; i+=2) {
    ans[i][0] = (i % 4 == 3 ? 0 : 1);
    ans[i+1][0] = (i % 4 == 3 ? 0 : 1);
    int bit = 12 - i / 2;
    for(int j=1; j<=N; j++) {
      int res = (j & (1 << bit));
      if(res) res = 1;
      int nxt;
      if(i != 25) {
        nxt = (j & (1 << (bit - 1)));
        if(nxt) nxt = 1;
        ans[i][j] = (res ? (ans[i][0] == 1 ? -1 : -2): i + 2 + nxt);
        ans[i+1][j] = (res ? i + 2 + nxt : (ans[i][0] == 1 ? -2 : -1));
      }
      else {
        ans[i][j] = (ans[i][0] == 1 ? -1 : -2);
        ans[i+1][j] = (ans[i][0] == 1 ? -2 : -1);
      }
      
    }
  }
  return ans;
}

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