제출 #1267793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267793		ThylOne	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	35 ms	1348 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 = 24;
  
  //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]++;
      }
    }
  }
  for(int x = 0 ; x <=N ; x++){
    for(int p = 7 ; p>= 0 ; p--)
      cerr << tern[x][p];
    cerr<<endl;
  }
  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[7][j] == 2){
          if(tern[7][j] == 0){
            ans[v][j] = (step%2==0?-1:-2);
          }
        }if(step==8){
          ans[v][j] = 0;
        }else{
          ans[v][j] = 3*step + (tern[j][8 - step -1] + 1);
        } 
      }
    }
  }

  return ans;
}

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