Submission #1230261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230261		dssfsuper2	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	17 ms	1096 KiB

prison

#include "prison.h"

#include <vector>
#include <iostream>
using namespace std;
#define all(x) (X).begin(), (x).end()

vector<int> mb(int N){
  int stn = 3*3*3*3*3*3*3;
  vector<int> repr;
  for(int num = stn;num>=1;num/=3){
    int cc = 0;
    while(num<=N){
      N-=num;
      cc++;
    }
    repr.push_back(cc);
  }
  return repr;
}
vector<vector<int>> devise_strategy(int N) {
  
  vector<vector<int>> s(23, vector<int>(N+1));
  for(int i=0;i<23;i++){
    if(i==0){
      s[i][0]=0;
      for(int j = 1;j<=N;j++){
        auto b3 = mb(j);
        s[i][j]=b3[0]+1;
      }
      continue;
    }
    int bnum=(i-1)%3;
    int nbid = ((i-1)/3);
    if(((i-1)/3)%2==0){
      s[i][0]=1;
      for(int j = 1;j<=N;j++){
        auto b3 = mb(j);
        //b3 is B bnum is A
        if (b3[nbid]<bnum)s[i][j]=-2;
        else if (b3[nbid]>bnum)s[i][j]=-1;
        else if (i<22)s[i][j]=3*(nbid+1)+b3[nbid+1]+1;
        else s[i][j]=0;
        if((i==19 || i==20 || i==21) && s[i][j]!=-2 && s[i][j]!=-1){
          if(b3[nbid+1]==0)s[i][j]=-2;
          else if(b3[nbid+1]==2)s[i][j]=-1;
          else s[i][j]=22;
        }
      }
    }
    else{
      s[i][0]=0;
      
      for(int j = 1;j<=N;j++){
        if(i==22){
          if(mb(j)[nbid]==0)s[i][j]=-1;
          else s[i][j]=-2;
          continue;
        }
     
        auto b3 = mb(j);
        if (b3[nbid]<bnum)s[i][j]=-1;
        else if (b3[nbid]>bnum)s[i][j]=-2;
        else if (i<22) s[i][j]=3*(nbid+1)+b3[nbid+1]+1;
        else s[i][j] = 0;
      }
    }
  }

  return s;
}

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