oj.uz

Submission #647573

# Submission time Handle Problem Language Result Execution time Memory
647573 2022-10-03T07:58:14 Z mircea_007 Floppy (RMI20_floppy) C++17
7 / 100
 1000 ms 6216 KB 
#include <vector>
#include <string>
#include <functional>

#include "floppy.h"

using vi = std::vector<int>;

#define magic_sauce inline __attribute__((always_inline))

magic_sauce int min( int a, int b ){ return a < b ? a : b; }

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;
  int *aint = new int[n * 4];

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

  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];

  //printf( "n = %d | aintn = %d\n", n, aintn );

  /*
  i = 0;
  for( int p2 = 1 ; p2 <= aintn ; p2 <<= 1 ){
    for( int j = 0 ; j < p2 ; j++ )
      printf( "%d ", aint[i + j] );
    printf( "\n" );
    i += p2;
  }*/

  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 *v = new int[N], *aint = new int[4 * N];
  int M = a.size(), i, aintn;
  vi ans;

  // 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
  aintn = 1;
  while( aintn < N )
    aintn <<= 1;

  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] ) );
  }

  return ans;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 672 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 4 ms 808 KB Output is correct
4 Correct 4 ms 672 KB Output is correct
5 Correct 4 ms 680 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 2780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 6216 KB Time limit exceeded
2 Halted 0 ms 0 KB -