Submission #626620

#	Time	Username	Problem	Language	Result	Execution time	Memory
626620		Monchito	Prisoner Challenge (IOI22_prison)	C++17	30 / 100	31 ms	2252 KiB

prison

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

typedef vector<int> vi;
typedef vector<vi> vvi;

map<int,pair<int,int>> mp1;
map<pair<int,int>,int> mp2;

void calc(){
  int cnt = 1;

  for(int i = 0; i <= 27; i++){
    for(int j = 0; j <= 1; j++){
      mp1[cnt] = make_pair(i, j);
      mp2[make_pair(i, j)] = cnt++;
    }
  }
}

vvi devise_strategy(int N){
  calc();
  vvi ret(57, vi(N+1,0));

  ret[0][0] = 0;
  for(int j = 1; j <= N; j++){
    int pos = 0;
    int bit = (j & (1 << 13)) >= 1;
    ret[0][j] = mp2[make_pair(pos, bit)];
  }  
  for(int i = 1; i <= 56; i++){
    auto& [pos, val] = mp1[i];
    ret[i][0] = pos <= 13;
    
    int k = (pos > 13) ? pos - 14 : pos;
    k = 13 - k;
    
    for(int j = 1; j <= N; j++){
      int bit = (j & (1 << k)) >= 1;

      if(k == 0 || bit != val){
        if(bit > val) ret[i][j] = (pos > 13) ? -2 : -1;
        else ret[i][j] = (pos > 13) ? -1 : -2;
      }
      else{
        pair<int,int> p;
        p.first = pos + 1 + ((pos > 13) ? -14 : 14);
        p.second = (j & (1 << (k - 1))) >= 1;
        ret[i][j] = mp2[p]; 
      }
    }
  }
  return ret;  
}

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