Submission #978108

#	Time	Username	Problem	Language	Result	Execution time	Memory
978108		mircea_007	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	10 ms	1116 KiB

prison

#include "prison.h"
#include <vector>
#include <stdio.h>

// solutie x = 24

/*

  strategie proasta:
    baza B, K cifre

    citesti cifra din A, scrii in stare
    compari: diferit => return
             egal => MAI TREBUIE O STARE DE REDIRECTIONARE

  cum repari:
    pentru deja stii valoarea lui B atunci scrii starea in functie de B

*/

namespace Solver {
  const int BASE = 3;
  const int DIGITS = 8;
  
  std::vector<int> pb;
  std::vector<int> getpb() {
    std::vector<int> ret( 1, 1 );
    while( (int)ret.size() <= DIGITS )
      ret.push_back( ret.back() * BASE );

    return ret;
  }

  int extract( int num, int idx ) {
    if( idx >= DIGITS )
      return -1;
    
    return (num / pb[DIGITS - idx - 1]) % BASE;
  }

  int beats( int win, int lose ) {
    if( win == 0 )
      return -2;
    return -1;
  }

  std::vector<std::vector<int>> devise_strategy( int N ) {
    pb = getpb(); // cum fac asta cu constexpr?
    
    // ret[y < x][0] = action
    std::vector<std::vector<int>> ret(1 + BASE * DIGITS, std::vector<int>(N + 1, 0)); // x = 24

    // starea initiala => citim 1
    ret[0][0] = 1;
    for( int val = 1 ; val <= N ; val++ )
      ret[0][val] = 1 + extract( val, 0 );

    for( int idx = 0 ; idx < DIGITS ; idx++ ){
      bool t = (idx & 1);
    
      for( int dig = 0 ; dig < BASE ; dig++ ){
        int state = 1 + idx * BASE + dig;
      
        ret[state][0] = t;
        for( int valt = 1 ; valt <= N ; valt++ ){
          int digt = extract( valt, idx );

          if( digt < dig )
            ret[state][valt] = beats( !t, t );
          else if( digt > dig )
            ret[state][valt] = beats( t, !t );
          else
            ret[state][valt] = 1 + BASE * (idx+1) + extract( valt, idx+1 ); // cifra idx+1 a lui t            
        }
      }
    }

    // scoate starile pe care nu le atingem
    for( auto &lin : ret )
      for( auto &el : lin )
        if( el >= (int)ret.size() )
          el = -1;

    return ret;
  }
}

std::vector<std::vector<int>> devise_strategy( int N ) {
  return Solver::devise_strategy( N );
}

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