Submission #494461

#	Time	Username	Problem	Language	Result	Execution time	Memory
494461		mircea_007	Floppy (RMI20_floppy)	C++17	0 / 100	95 ms	8528 KiB

floppy

#include "floppy.h"

#define MAXN 40000
#define MAXL 16

std::string _out;

void dfs( int l, int r, const std::vector<int> &v ){
  int i, max = l, hasleft, hasright;
  char newch[3] = { '\0', '\0', '\0' };
  
  //printf("[%d, %d]\n", l, r);
  
  for( i = l + 1 ; i <= r ; i++ )
    max = v[i] > v[max] ? i : max;
  
  newch[0] = '0' + (hasleft = (max > l));
  newch[1] = '0' + (hasright = (max < r));
  _out.append(newch);
  
  if( hasleft )
    dfs(l, max - 1, v);
  if( hasright )
    dfs(max + 1, r, v);
}

void read_array( int subtask_id, const std::vector<int> &v ){
  _out.clear();
  
  dfs(0, v.size() - 1, v);
  
  save_to_floppy(_out);
}

int rebuild( int v[], const std::string &bits, int min, int pozv, int pozb ){
  int i, hasleft, hasright, lleft, lright;
  
  hasleft  = bits[pozb    ] - '0';
  hasright = bits[pozb + 1] - '0';
  
  pozb += 2;
  
  if( hasleft ){
    lleft = rebuild(v, bits, min, pozv, pozb);
    min += lleft;
    pozv += lleft;
    pozb += 2 * lleft;
  }else
    lleft = 0;
  
  i = pozv++;// retinem locul unde se afla maximul
  
  if( hasright ){
    lright = rebuild(v, bits, min, pozv, pozb);
    min += lright;
  }else
    lright = 0;
  
  v[i] = min;
  
  return lleft + lright + 1;
}

int _v[MAXN];
int _n;
std::vector<int> _answers;
int _rmq[MAXN][MAXL];
int _log[MAXN + 1];

void RMQinit(){
  int i, l, p2;
  
  _log[0] = _log[1] = 0;
  for( i = 2 ; i <= _n ; i++ )
    _log[i] = 1 + _log[i >> 1];
  
  for( i = 0 ; i < _n ; i++ )
    _rmq[0][i] = i;
  
  l = 1;
  for( p2 = 1 ; p2 * 2 <= _n ; p2 <<= 1 ){
    for( i = 0 ; i + 2 * p2 <= _n ; i++ )
      _rmq[l][i] = _v[_rmq[l - 1][i]] > _v[_rmq[l - 1][i + p2]] ? _rmq[l - 1][i] : _rmq[l - 1][i + p2];

    l++;
  }
}

int RMQquery( int l, int r ){
  int _loglr = _log[r - l + 1], p2;
  p2 = (1 << _loglr);

  return _v[_rmq[_loglr][l]] > _v[_rmq[_loglr][r - p2 + 1]] ? _rmq[_loglr][l] : _rmq[_loglr][r - p2 + 1];
}

std::vector<int> solve_queries( int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b ){
  int i;
  _n = rebuild(_v, bits, 0, 0, 0);
  
  if( _n != N ){
    fprintf(stderr, "(!) CRITICAL: n not the same!!!! (%d != %d)\n", _n, N);
    exit(1);
  }

  RMQinit();
  
  for( i = 0 ; i < (int)a.size() ; i++ )
    _answers.push_back(RMQquery(a[i], b[i]));
  
  return _answers;
}

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: 0 / 7
• Subtask 2: 0 / 21
• Subtask 3: 0 / 72