oj.uz

Submission #967832

# Submission time Handle Problem Language Result Execution time Memory
967832 2024-04-23T01:28:36 Z NK_ Floppy (RMI20_floppy) C++17
100 / 100
 75 ms 20868 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;
using str = string;

V<vi> build(const vi& A) {
    auto cmb = [&](int a, int b) { return (A[a] > A[b] ? a : b); };

    int N = sz(A);
    V<vi> jmp = {vi(N)}; iota(begin(jmp[0]), end(jmp[0]), 0);
    for(int i = 1; (1 << i) <= N; i++) {
        jmp.pb(vi(N - (1 << i) + 1));
        for(int x = 0; x < sz(jmp[i]); x++) {
            jmp[i][x] = cmb(jmp[i - 1][x], jmp[i - 1][x + (1 << (i - 1))]);
        }
    }

    return jmp;
}

void read_array(int id, const vi &A) {
    // cout << "HERE" << endl;
    auto cmb = [&](int a, int b) { return (A[a] > A[b] ? a : b); };

    V<vi> st = build(A);
    auto qry = [&](int l, int r) {
        if (l == r) return l;
        int d = 31 - __builtin_clz(r - l + 1);
        return cmb(st[d][l], st[d][r - (1 << d) + 1]);
    };

    str S;
    function<void(int, int)> dnc = [&](int l, int r) {
        if (l > r) return;

        int m = qry(l, r);
        // cout << l << " " << m << " " << r << endl;
        S += char('0' + (l != m));
        S += char('0' + (r != m));

        dnc(l, m - 1); dnc(m + 1, r);
    };

    dnc(0, sz(A) - 1);

    save_to_floppy(S);
}

vi solve_queries(int id, int N, const str &S, const vi &L, const vi &R) {
    vi ans;

    vi A; int cur = 0;
    function<void(int, int)> dfs = [&](int u, int d) {
        // cout << u << " => " << S[2 * u] << " " << S[2 * u + 1] << endl;
        if (S[2 * u] == '1') dfs(++cur, d - 1);
        A.pb(d);
        if (S[2 * u + 1] == '1') dfs(++cur, d - 1);
    };

    dfs(0, N);

    // for(auto& x : A) cout << x << " ";
    // cout << endl;

    auto cmb = [&](int a, int b) { return (A[a] > A[b] ? a : b); };

    V<vi> st = build(A);
    auto qry = [&](int l, int r) {
        if (l == r) return l;
        int d = 31 - __builtin_clz(r - l + 1);
        return cmb(st[d][l], st[d][r - (1 << d) + 1]);
    };

    for(int i = 0; i < sz(L); i++) ans.pb(qry(L[i], R[i]));
    return ans;
}

// g++-13 -std=c++17 -O2 grader.cpp A.cpp -o ./G

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 816 KB Output is correct
2 Correct 2 ms 824 KB Output is correct
3 Correct 1 ms 820 KB Output is correct
4 Correct 1 ms 828 KB Output is correct
5 Correct 1 ms 828 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4484 KB Output is correct
2 Correct 16 ms 4548 KB Output is correct
3 Correct 17 ms 5384 KB Output is correct
4 Correct 17 ms 5052 KB Output is correct
5 Correct 16 ms 4528 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 16580 KB Output is correct
2 Correct 69 ms 16548 KB Output is correct
3 Correct 75 ms 20868 KB Output is correct
4 Correct 68 ms 18716 KB Output is correct
5 Correct 70 ms 16376 KB Output is correct