Submission #398504

#	Time	Username	Problem	Language	Result	Execution time	Memory
398504		model_code	Floppy (RMI20_floppy)	C++17	28 / 100	142 ms	3232 KiB

floppy

/**
* user:  andreescu-405
* fname: Mihnea
* lname: Andreescu
* task:  Floppy
* score: 28.0
* date:  2020-12-03 08:36:30.524445
*/
#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

/**
string memo;

void save_to_floppy(const std::string &bits) {
  memo = bits;
}**/

void read_array(int subtask_id, const std::vector<int> &v) {
  string ret;
  int n = (int) v.size(), k = log2(n) + 1;
  vector<int> stk;
  for (int i = 0; i < n; i++) {
    while (!stk.empty() && v[i] > v[stk.back()]) {
      stk.pop_back();
    }
    int j;
    if (stk.empty()) {
      j = 0;
    } else {
      j = stk.back() + 1;
    }
    stk.push_back(i);
    for (int bit = 0; bit < k; bit++) {
      if (j & (1 << bit)) ret += '1';
      else ret += '0';
    }
  }
  save_to_floppy(ret);
}

const int N = 40000;
const int K = 17;
///int tab[K][N];
int go[N];

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 k = log2(n) + 1;
  for (int i = 0; i < n; i++) {
    int j = 0;
    for (int pos = i * k; pos < (i + 1) * k; pos++) {
      if (bits[pos] == '1') {
        j += (1 << (pos - i * k));
      }
    }
    go[i + 1] = j;
    ///tab[0][i + 1] = j;
  }
  /**for (int k2 = 1; k2 <= k; k2++) {
    for (int i = 1; i <= n; i++) {
      tab[k2][i] = tab[k2 - 1][tab[k2 - 1][i]];
    }
  }**/
  vector<int> ret;
  for (int it = 0; it < (int) a.size(); it++) {
    int l = a[it] + 1, r = b[it] + 1;
    /**for (int k2 = k; k2 >= 0; k2--) {
      if (tab[k2][r] >= l) {
        r = tab[k2][r];
      }
    }**/
    while (go[r] >= l) {
      r = go[r];
    }
    ret.push_back(r - 1);
  }
  return ret;
}

/**
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  read_array(3, {40, 20, 30, 10});
  auto ret = solve_queries(3, 4, memo, {0 , 0 , 0 , 0 , 1 , 1 , 1 , 2 , 2 , 3}, {0 , 1 , 2 , 3 , 1 , 2 , 3 , 2 , 3 , 3});
  for (auto &x : ret) {
    cout << x << " ";
  }
  cout << "\n";
}
**/

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 0 / 72