Submission #1117116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117116		SonicML	Floppy (RMI20_floppy)	C++14	100 / 100	70 ms	17488 KiB

floppy

#include <stdlib.h>
#include <string>
#include <vector>

#include "floppy.h"

using namespace std;

int n;

int const INF = 1e9+7;

int const NMAX = 40000;
int arr[1 + NMAX];
string ans1;

int ind = 0;

bool compareArr(int a, int b) {
  return (arr[a] < arr[b]);
}

int const KMAX = 16;
int rmq[1 + KMAX][1 + NMAX];

void buildRMQ() {
  for(int i = 1;i <= n;i++) {
    rmq[0][i] = i;
  } 
  for(int k = 1;k < KMAX;k++) {
    for(int i = 1;i <= n;i++) {
      int ii = min(n, i+(1<<(k-1)));
      if(compareArr(rmq[k-1][i], rmq[k-1][ii])) {
        rmq[k][i] = rmq[k-1][i];
      }else {
        rmq[k][i] = rmq[k-1][ii];
      }
    }
  }
}

int answerQuery(int from, int to) {
  int leng = (to - from + 1); 
  int k = (31 - __builtin_clz(leng));
  if(compareArr(rmq[k][from], rmq[k][to-(1<<k)+1])) {
    return rmq[k][from];
  } else {
    return rmq[k][to-(1<<k)+1];
  }
}

void buildGraph(int from, int to) {
  if(from <= to) {
    int root = answerQuery(from, to);
    int node = ind;
    ans1[node * 2] = ans1[node * 2 + 1] = '0';
    if(from < root) {
      ans1[node * 2] = '1';
      ind++;
      buildGraph(from, root-1);
    }
    if(root < to) {
      ans1[node * 2 + 1] = '1';
      ind++;
      buildGraph(root+1, to);
    }
  }
}

void read_array(int subtask_id, const std::vector<int> &v) {
  ind = 0;
  n = v.size(); 
  for(int i = 1;i <= n;i++) {
    arr[i] = -v[i-1];
  }
  buildRMQ();
  ans1.resize(2 * n);
  buildGraph(1, n);
  save_to_floppy(ans1);
}

int pos[1 + NMAX];
int nextNode = 0;

void buildPos(int node) {
  if(ans1[node * 2] == '1') {
    nextNode++; 
    buildPos(nextNode);
  }
  ind++;
  pos[node] = ind;
  if(ans1[node * 2 + 1] == '1') {
    nextNode++;
    buildPos(nextNode);
  }
  return;
}


std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) { 
  n = N;
  ind = 0;
  ans1 = bits;
  buildPos(0);
  for(int i = 0;i < n;i++) {
    arr[pos[i]] = i;
  }
  buildRMQ();
  vector <int> ans2; 
  for(int i = 0;i < a.size();i++) {
    ans2.push_back(answerQuery(a[i]+1, b[i]+1)-1);
  }
  return ans2;
}

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i = 0;i < a.size();i++) {
      |                 ~~^~~~~~~~~~
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