oj.uz

Submission #800173

# Submission time Handle Problem Language Result Execution time Memory
800173 2023-08-01T11:16:47 Z M7kra Floppy (RMI20_floppy) C++17
7 / 100
 30 ms 3904 KB 
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;

#include "floppy.h"

struct Bits {
    string bits = "";

    void add(bool b) {
        if (b) bits += "1";
        else bits += "0";
    }

    string get() {
        return bits;
    }
};

void read_array(int subtask_id, const std::vector<int> &v) {
    vector<int> numbers(v);
    Bits bits;
    sort(numbers.begin(), numbers.end(), [&bits](int a, int b) mutable {
        bits.add(a < b);
        return a < b;
    });
    //cout << bits.get() << "\n";
    save_to_floppy(bits.get());
}

struct DBits {
    string bits;
    int index;

    DBits(string bits) {
        this->bits = bits;
        index = 0;
    }

    bool get() {
        return bits[index++] == '1';
    }
};

struct STree {
    int n;
    vector<int> elements;
    vector<int> best_index;

    STree (int size) {
        n = best2power(size);
        elements = vector<int>(n * 2);
        best_index = vector<int>(n * 2);
    }

    void update(int k, int x) {
        k += n;
        elements[k] = x;
        best_index[k] = k - n;
        for (k /= 2; k >= 1; k /= 2) {
            int a = k * 2;
            int b = a + 1;
            if (elements[a] > elements[b]) {
                elements[k] = elements[a];
                best_index[k] = best_index[a];
            } else {
                elements[k] = elements[b];
                best_index[k] = best_index[b];
            }
        }
    }

    int get(int a, int b) {
        a += n;
        b += n;
        int best = -1;
        int index = -1;
        while (a <= b) {
            if (a & 1) {
                if (elements[a] > best) {
                    best = elements[a];
                    index = best_index[a];
                }
                a++;
            }
            if ((b & 1) == 0) {
                if (elements[b] > best) {
                    best = elements[b];
                    index = best_index[b];
                }
                b--;
            }
            a /= 2;
            b /= 2;
        }
        return index;
    }

    int best2power(int n) {
        int i = 1;
        while (i < n) i *= 2;
        return i;
    }
};

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    DBits dbits(bits);

    vector<int> numbers(N);
    for (int i = 0; i < N; i++) numbers[i] = i;
    sort(numbers.begin(), numbers.end(), [&dbits](int a, int b) {
        return dbits.get();
    });
    vector<int> result(N);
    for (int i = 0; i < N; i++) result[numbers[i]] = i;
    /*for (int i = 0; i < N; i++) {
        if (i) cout << " ";
        cout << result[i];
    }
    cout << "\n";*/

    STree stree(N);
    for (int i = 0; i < N; i++) {
        stree.update(i, result[i]);
    }

    vector<int> answers(a.size());
    for (int i = 0; i < a.size(); i++) {
        answers[i] = stree.get(a[i], b[i]);
    }

    return answers;
}

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 796 KB Output is correct
2 Correct 2 ms 800 KB Output is correct
3 Correct 2 ms 664 KB Output is correct
4 Correct 2 ms 788 KB Output is correct
5 Correct 2 ms 788 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Partially correct 30 ms 3904 KB Partially correct
2 Partially correct 27 ms 3832 KB Partially correct
3 Partially correct 25 ms 3652 KB Partially correct
4 Incorrect 7 ms 1580 KB L is too large
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

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