Submission #1224310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224310		Ghulam_Junaid	Floppy (RMI20_floppy)	C++20	28 / 100	61 ms	2912 KiB

floppy

#include <bits/stdc++.h>
#include <stdlib.h>
#include <string.h>
#include "floppy.h"
using namespace std;

void read_array(int subtask_id, const vector<int> &v) {
    string bits;
    int n = v.size();
    int lg = 31 - __builtin_clz(n) + 1;
    
    vector<pair<int, int>> vec;
    for (int i = 0; i < n; i ++)
        vec.push_back({v[i], i});
    sort(vec.begin(), vec.end());

    for (auto [x, i] : vec){
        for (int b = 0; b < lg; b ++){
            if ((1 << b) & i)
                bits += '1';
            else
                bits += '0';
        }
    }

    save_to_floppy(bits);
}

string bits;
int n;
char ask(int i, int j){
    return bits[(j - 1) * n + i];
}

vector<int> solve_queries(int subtask_id, int nn,
        const string &ss,
        const vector<int> &a, const vector<int> &b) {
    bits = ss, n = nn;
    int pos[n];
    int lg = 31 - __builtin_clz(n) + 1;
    
    vector<int> order;
    for (int i = 0; i < n; i ++){
        int ind = 0;
        for (int b = 0; b < lg; b ++)
            if (bits[i * lg + b] == '1')
                ind += 1 << b;
        pos[ind] = order.size();
        order.push_back(ind);
    }

    vector<int> answers;
    for (int i = 0; i < a.size(); i ++){
        int l = a[i], r = b[i];
        int mx = 0;
        for (int j = l; j <= r; j ++)
            mx = max(mx, pos[j]);
        answers.push_back(order[mx]);   
    }
    return answers;
}

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