oj.uz

Submission #398504

# Submission time Handle Problem Language Result Execution time Memory
398504 2021-05-04T12:28:48 Z model_code Floppy (RMI20_floppy) C++17
28 / 100
 142 ms 3232 KB 
/**
* 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 636 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3232 KB Output is correct
2 Correct 42 ms 3084 KB Output is correct
3 Correct 142 ms 3216 KB Output is correct
4 Correct 46 ms 3208 KB Output is correct
5 Correct 40 ms 3072 KB Output is correct

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 2736 KB L is too large
2 Halted 0 ms 0 KB -