Submission #978119

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

prison

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

//#include <stdio.h>

namespace Solver {
  std::vector<int> opt_split;
  std::vector<int> nrstates; // nrstates[i] =def= numarul de stari necesare distingerii unui interval de lungime i

  int ceil( int a, int b ) {
    if( !a )
      return 0;
    return (a - 1) / b + 1;
  }

  void get_stats( int N ) {
    nrstates.resize( N + 1, 0 );
    opt_split.resize( N + 1, 0 );

    opt_split[3] = 1;
    nrstates[3] = 1;
    for( int n = 4 ; n <= N ; n++ ){
      if( 2 + nrstates[ceil( n - 2, 2 )] < 3 + nrstates[ceil( n - 2, 3 )] ){
        nrstates[n] = 2 + nrstates[ceil( n - 2, 2 )];
        opt_split[n] = 2;
      }else{
        nrstates[n] = 3 + nrstates[ceil( n - 2, 3 )];
        opt_split[n] = 3;
      }
    }
  }

  // strategy
  std::vector<int> split_len; // lungimea intervalului pe care trebuie sa il distingem
  std::vector<int> splits;    // numarul de bucket-uri pe care il folosim
  std::vector<int> buk;       // lungimea bucketului pe care il folosim
  std::vector<std::vector<int>> poz_in_split; // pozitia in intervalul original pe care tb sa il distingem

  std::vector<int> start_idx;

  const int NIL = -1;

  void strategy_stats( int N ) {
    split_len.push_back( N );
    poz_in_split.emplace_back( N + 1 );
    for( int val = 1 ; val <= N ; val++ )
      poz_in_split[0][val] = val - 1;
    
    while( split_len.back() >= 3 ){
      int L = split_len.back();

      int S = opt_split[L];
      splits.push_back( S );

      int B = ceil( L - 2, S );
      buk.push_back( B );

      int idx = (int)poz_in_split.size() - 1;
      poz_in_split.emplace_back( N + 1 );
      for( int val = 1 ; val <= N ; val++ ){
        int pis = poz_in_split[idx][val];

        if( pis == NIL || pis == 0 || pis == L - 1 )
          poz_in_split[idx+1][val] = NIL;
        else
          poz_in_split[idx+1][val] = (poz_in_split[idx][val] - 1) % B;
      }

      split_len.push_back( B );
    }

    // sume partiale
    start_idx.push_back( 1 );
    for( int S : splits )
      start_idx.push_back( start_idx.back() + S );
  }

  int beats( int win, int lose ) {
    if( lose == 0 )
      return -1;
    return -2;
  }
  
  std::vector<std::vector<int>> devise_strategy( int N ) {
    get_stats( N );
    strategy_stats( N );

    std::vector<int> ret_idx;
    std::vector<std::vector<int>> ret;

    ret.emplace_back( N+1 );

    bool t = 0;
    ret[0][0] = t;
    for( int val = 1 ; val <= N ; val++ ){
      int P = poz_in_split[0][val];
      
      if( P == 0 )
        ret[0][val] = beats( !t, t );
      else if( P == N - 1 )
        ret[0][val] = beats( t, !t );
      else if( (int)splits.size() )
        ret[0][val] = start_idx[0] + (P - 1) / buk[0];
    }
    
    for( int idx = 0 ; idx < (int)splits.size() ; idx++ ){
      t = !t;

      // valori precalculate
      int L = split_len[idx];
      int B = buk[idx];
      int S = splits[idx];

      // state = start_idx[idx] + ((poz_in_split - 1) / B)

      // asiguram ca am alocat memoria
      int SI = start_idx[idx];
      while( (int)ret.size() < SI + S ){
        int buk_idx = (int)ret.size() - SI;

        ret.emplace_back( N + 1 );
        ret.back()[0] = t;

        for( int val = 1 ; val <= N ; val++ ){
          int P = poz_in_split[idx][val];

          if( P == NIL )
            ret.back()[val] = 0; // nu conteaza
          else if( P == 0 )
            ret.back()[val] = beats( !t, t );
          else if( P == L - 1 )
            ret.back()[val] = beats( t, !t );
          else{
            int t_buk_idx = (P - 1) / B;

            if( t_buk_idx < buk_idx )
              ret.back()[val] = beats( !t, t );
            else if( t_buk_idx > buk_idx )
              ret.back()[val] = beats( t, !t );
            else{
              int P2 = (P - 1) % B;
              if( P2 == 0 )
                ret.back()[val] = beats( !t, t );
              else if( P2 == B - 1 )
                ret.back()[val] = beats( t, !t );
              else if( idx+1 < (int)splits.size() ) // evitam depasirea
                ret.back()[val] = start_idx[idx+1] + (P2 - 1) / buk[idx+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: 90 / 90