Submission #800180

#	Time	Username	Problem	Language	Result	Execution time	Memory
800180		M7kra	Floppy (RMI20_floppy)	C++17	28 / 100	26 ms	6624 KiB

floppy

#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;
    stable_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;
    stable_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 (stderr)

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 / 7
• Subtask 2: 21 / 21
• Subtask 3: 0 / 72