oj.uz

Submission #647581

# Submission time Handle Problem Language Result Execution time Memory
647581 2022-10-03T08:38:10 Z mircea_007 Floppy (RMI20_floppy) C++17
100 / 100
 140 ms 17664 KB 
#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

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 2 ms 536 KB Output is correct
2 Correct 2 ms 528 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 2 ms 536 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2712 KB Output is correct
2 Correct 30 ms 3392 KB Output is correct
3 Correct 32 ms 4844 KB Output is correct
4 Correct 32 ms 4196 KB Output is correct
5 Correct 38 ms 3472 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 9164 KB Output is correct
2 Correct 117 ms 12176 KB Output is correct
3 Correct 140 ms 17664 KB Output is correct
4 Correct 137 ms 14836 KB Output is correct
5 Correct 132 ms 12232 KB Output is correct