Submission #1267802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267802		ThylOne	Prisoner Challenge (IOI22_prison)	C++20	0 / 100	3 ms	836 KiB

prison

#include "prison.h"

#include <vector>
#include <array>
#include <cmath>
#include <iostream>
#include <cassert>


using namespace std;

std::vector<std::vector<int>> devise_strategy(int N) {
  const int maxV = 22;
  
  //on calcul les puissances de 3
  int powers[8];
  powers[0]=1;
  for(int i=1;i<8;i++)powers[i] = 3 * powers[i-1];
  
  std::array<int, 8> tern[5001];
  for(int v = 0 ; v <= 5000 ; v++){
    int act = v;
    for(int i = 7 ; i >=0; i--){
      tern[v][i] = 0;
      while(powers[i]<=act){
        act -= powers[i];
        tern[v][i]++;
      }
    }
  }
  
  std::vector<std::vector<int>> ans(maxV + 1,std::vector<int>(N + 1,0));
  ans[0][0] = 0; //on regarde A en premier
  for(int j = 1 ; j <= N ; j++)ans[0][j] = tern[j][7] + 1;
  for(int v = 1 ; v < maxV ; v++){
    const int step = (v-1)/3+1;
    cerr<<v << " " << step << endl;
    const int target((v-1)%3);

    if(step%2 == 1)ans[v][0] = 1;
    else ans[v][0] = 0;

    for(int j = 1 ; j<= N ; j++){
      if(target < tern[j][8 - step]){
        ans[v][j] = (step%2==1?-1:-2);
      }else if(target > tern[j][8 - step]){
        ans[v][j] = (step%2==1?-2:-1);
      }else{
        //equal
        if(step==7 && tern[j][0] == 2){
          ans[v][j] = (step%2==0?-2:-1);
        }else if(step==7 && tern[j][0] == 0){
          ans[v][j] = (step%2==1?-2:-1);
        }else if(step==7){
          ans[v][j] = 22;
        }else if(step==8){
          ans[v][j] = 0;
        }else{
          ans[v][j] = 3*step + (tern[j][8 - step -1] + 1);
        } 
      }
    }
  }
  for(int j = 1 ; j <= N ; j++){
    ans[22][j] = (tern[j][0]==1?-1:-2);
  }

  return ans;
}

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