Submission #1221836

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

floppy

#include <stdlib.h>
#include <string.h>

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

void read_array(int subtask_id, const vector<int> &v) {
    int n = v.size();
    int l = floor(log2(n));
    vector<pair<int, int>> vq {};
    for (int i = 0; i < n; i++) {
        vq.push_back({v[i], i});
    }
    vector<int> ord (n, -1);
    sort(vq.begin(), vq.end());
    for (int i = 0; i < n; i++) {
        ord[vq[i].second] = i;
    }
    
    string bits = "";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= l; j++) {
            if ((ord[i] >> j) & 1) bits += "1";
            else bits += "0";
        }
    }
    
    save_to_floppy(bits);
}

vector<int> solve_queries(int subtask_id, int N,
        const string &bits,
        const vector<int> &a, const vector<int> &b) {
    int l = floor(log2(N));
    vector<int> ord (N, 0);
    int cur = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= l; j++) {
            if (bits[cur] == '1') ord[i] += 1 << j;
            cur++;
        }
    }

    int k = sqrt(N);
    int nk = (N-1)/k + 1;
    vector<int> vb (nk, -1);
    vector<int> vind (nk, -1);
    for (int i = 0; i < N; i++) {
        if (vb[i/k] < ord[i]) {
            vb[i/k] = ord[i];
            vind[i/k] = i;
        }
    }

    vector<int> ans (a.size(), 0);
    for (int i = 0; i < a.size(); i++) {
        int sol = -1;
        int id = -1;
        int lo = a[i];
        int r = b[i];
        while (lo <= r) {
            if (lo%k == 0 && lo + k <= r) {
                if (sol < vb[lo/k]) {
                    sol = vb[lo/k];
                    id = vind[lo/k];
                }
                lo += k;
            } else {
                if (sol < ord[lo]) {
                    sol = ord[lo];
                    id = lo;
                }
                lo++;
            }
        }
        ans[i] = id;
    }
    return ans;
}

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