Submission #647581

#	Time	Username	Problem	Language	Result	Execution time	Memory
647581		mircea_007	Floppy (RMI20_floppy)	C++17	100 / 100	140 ms	17664 KiB

floppy

#include <vector>
#include <string>
#include <functional>

#include "floppy.h"

using vi = std::vector<int>;

#define magic_sauce inline __attribute__((always_inline))

template<typename T> int query( int *aint, T &v, int root, int rl, int rr, int ql, int qr ){
  int mij = (rl + rr) >> 1;

  if( rl == ql && rr == qr ) return aint[root];
  if( ql >  mij ) return query( aint, v, root * 2 + 2, mij+1, rr, ql, qr );
  if( qr <= mij ) return query( aint, v, root * 2 + 1, rl, mij, ql, qr );

  int retl = query( aint, v, root * 2 + 1, rl, mij, ql, mij );
  int retr = query( aint, v, root * 2 + 2, mij+1, rr, mij+1, qr );

  return v[retl] > v[retr] ? retl : retr;
};

// transmit

void read_array( int subtask_id, const vi &v ){
  int n = v.size(), i, aintn = 1;
  while( aintn < n )
    aintn <<= 1;

  int *aint = new int[2 * aintn];

  for( i = 0 ; i < n ; i++ )
    aint[aintn - 1 + i] = i;
  for( i = n ; i < aintn ; i++ )
    aint[aintn - 1 + i] = 0;
  for( i = aintn - 1 ; i-- ; )
    aint[i] = v[aint[i * 2 + 1]] > v[aint[i * 2 + 2]] ? aint[i * 2 + 1] : aint[i * 2 + 2];

  std::string msg = "";

  std::function<void( int, int )> dfs = [&]( int l, int r ) -> void {
    if( l > r ) return;

    int mij = query( aint, v, 0, 0, aintn - 1, l, r );

    msg.push_back( (char)('0' + (mij > l)) );
    msg.push_back( (char)('0' + (mij < r)) );

    dfs( l, mij - 1 );
    dfs( mij + 1, r );
  };

  dfs( 0, n - 1 );

  save_to_floppy( msg );

  delete []aint;
}

// recieve

vi solve_queries( int subtask_id, int N, const std::string &bits, const vi &a, const vi &b ){
  int M = a.size(), i, aintn = 1;
  vi ans;

  while( aintn < N )
    aintn <<= 1;

  int *v = new int[N], *aint = new int[2 * aintn];

  // reconstruct array
  std::function<int( int, int, int )> dfs = [&]( int root, int start, int maxv ) -> int { // root is an index in bits and start is and index in v
    int hasl = bits[root] - '0', hasr = bits[root + 1] - '0';
    int sizel = 0, sizer = 0;

    if( hasl )
      sizel = dfs( root + 2, start, maxv - 1 );
    v[start + sizel] = maxv;
    if( hasr )
      sizer = dfs( root + 2 + (sizel << 1), start + sizel + 1, maxv - 1 );

    return 1 + sizel + sizer;
  };

  dfs( 0, 0, N );

  // build segment tree
  for( i = 0 ; i < N ; i++ )
    aint[aintn - 1 + i] = i;
  for( i = N ; i < aintn ; i++ )
    aint[aintn - 1 + i] = 0;
  for( i = aintn - 1 ; i-- ; )
    aint[i] = v[aint[i * 2 + 1]] > v[aint[i * 2 + 2]] ? aint[i * 2 + 1] : aint[i * 2 + 2];

  ans.clear();
  for( i = 0 ; i < M ; i++ ){
    ans.push_back( query( aint, v, 0, 0, aintn - 1, a[i], b[i] ) );
  }

  delete []v;
  delete []aint;

  return ans;
}

Compilation message (stderr)

stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72