Submission #901470

#	Time	Username	Problem	Language	Result	Execution time	Memory
901470		nguyentunglam	Floppy (RMI20_floppy)	C++17	100 / 100	87 ms	58036 KiB

floppy

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

#include "floppy.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, M = 17;

struct encode {

string ret;

int T[N << 2], a[N];

int n;

int best(int x, int y) {
  return a[x] > a[y] ? x : y;
}

void build(int s, int l, int r) {
  if (l == r) {
    T[s] = l;
    return;
  }
  int mid = l + r >> 1;
  build(s << 1, l, mid);
  build(s << 1 | 1, mid + 1, r);
  T[s] = best(T[s << 1], T[s << 1 | 1]);
}

int get(int s, int l, int r, int from, int to) {
  if (l > to || r < from) return from;
  if (from <= l && r <= to) return T[s];
  int mid = l + r >> 1;
  return best(get(s << 1, l, mid, from, to), get(s << 1 | 1, mid + 1, r, from, to));
}

void decartes (int l, int r) {
  int j = get(1, 0, n - 1, l, r);
//  cout << l << " " << r << " " << j << endl;
  if (j > l) {
    ret.push_back('1');
    decartes(l, j - 1);
  }
  else ret.push_back('0');
  if (j < r) {
    ret.push_back('1');
    decartes(j + 1, r);
  }
  else ret.push_back('0');
}

string read_array(int subtask_id, const std::vector<int> &v) {
  n = v.size();

  for(int i = 0; i < n; i++) a[i] = v[i];

  build(1, 0, n - 1);

  decartes(0, n - 1);
  return ret;
}
} encode;

void read_array(int subtask_id, const std::vector<int> &v) {
  save_to_floppy(encode.read_array(subtask_id, v));
}

struct decode {

int n, cnt = 0, idnode, h[N];

int p[M + 1][N];

bool bit[N];

int dfs(int dep) {
  int child0 = n, child1 = n;
  if (bit[cnt++]) child0 = dfs(dep + 1);
  int idx = idnode++;
  if (bit[cnt++]) child1 = dfs(dep + 1);
  h[idx] = dep;
//  if (child0 != n) cout << child0 << " " << idx << endl;
//  if (child1 != n) cout << child1 << " " << idx << endl;
  p[0][child0] = idx;
  p[0][child1] = idx;
  return idx;
}

int lca(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  int delta = h[u] - h[v];
  for(int j = 0; j <= M; j++) if (delta >> j & 1) u = p[j][u];
  if (u == v) return u;
  for(int j = M; j >= 0; j--) if (p[j][u] != p[j][v]) {
    u = p[j][u];
    v = p[j][v];
  }
  return p[0][u];
}

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;
  for(int i = 0; i < bits.size(); i++) bit[i] = bits[i] - '0';
  std::vector<int> answers(a.size());

  dfs(0);

  for(int j = 1; j <= M; j++) for(int i = 0; i < n; i++) p[j][i] = p[j - 1][p[j - 1][i]];

  for(int i = 0; i < a.size(); i++) {
    answers[i] = lca(a[i], b[i]);
//    cout << answers[i] << endl;
  }

  return answers;
}
} decode;

vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
  return decode.solve_queries(subtask_id, N, bits, a, b);
}

Compilation message (stderr)

floppy.cpp: In member function 'void encode::build(int, int, int)':
floppy.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int mid = l + r >> 1;
      |             ~~^~~
floppy.cpp: In member function 'int encode::get(int, int, int, int, int)':
floppy.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = l + r >> 1;
      |             ~~^~~
floppy.cpp: In member function 'std::vector<int> decode::solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i = 0; i < bits.size(); i++) bit[i] = bits[i] - '0';
      |                  ~~^~~~~~~~~~~~~
floppy.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   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