Submission #643361

#	Time	Username	Problem	Language	Result	Execution time	Memory
643361		TimDee	Floppy (RMI20_floppy)	C++17	0 / 100	104 ms	15172 KiB

floppy

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

int n;
vector<int> V;

void read_array(int subtask_id, const std::vector<int> &v) {
    n=v.size();
    V=v;
    vector<pair<int,int>> a(n);
    for (int i=0; i<n; ++i) a[i]={V[i],i};
    sort(a.begin(), a.end());
    for(int i=0; i<n; ++i) V[a[i].second]=i+1;
    
    string s;
    for (int i=0; i<n; ++i) {
        int x=V[i]/(i+1);
        int k=log2(n/(i+1))+1;
        for (int b=k-1; b>=0; --b) {
            s+=(char)('0'+((x>>b)&1));
        }
    }
    save_to_floppy(s);

}

vector<int> t;
vector<int> A;
int sz=1, neutr; 

int merge (int i, int j) {
    if (A[i]>A[j]) return i;
    else return j;
}

void update(int i, int l, int r) {
    if (r-l==1) return;
    int mid=(l+r)>>1;
    update(2*i+1,l,mid);
    update(2*i+2,mid,r);
    t[i]=merge(t[2*i+1],t[2*i+2]);
}

int query(int i, int l, int r, int lx, int rx) {
    if (l>=rx) return neutr;
    if (r<=lx) return neutr;
    if (l>=lx && r<=rx) return t[i];
    int mid=(l+r)>>1;
    int L=query(2*i+1,l,mid,lx,rx), R=query(2*i+2,mid,r,lx,rx);
    return merge(L,R);
}

int query(int l, int r) {
    return query(0,0,sz,l,r);
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    int n=N,m=a.size();
    while (sz<n) sz<<=1;
    t.assign(2*sz-1,n);
    string S=bits;
    vector<int> v(n);
    vector<int> vec(n);

    int last=0;
    for (int i=0; i<n; ++i) {
        int k=log2(n/(i+1))+1;
        int x=0;
        for (int b=k-1; b>=0; --b) x+=(S[last+k-1-b]-'0')<<b;
        vec[i]=x;
        last+=k;
    }

    vector<pair<int,int>> p(n+1);
    vector<vector<int>> vecc(n+3);
    for (int i=1; i<=n; ++i) {
        if (vec[i-1]==0) p[i].first=i;
        else p[i].first=min(((vec[i-1]+1)*(i)-1),n);
        if (vec[i-1]==0) p[i].second=1;
        else p[i].second=vec[i-1]*i;
        vecc[p[i].first].push_back(i);
    }

    multiset<pair<int,int>>lol;
    for(int i=n;i>=1;i--){
        for(auto it : vecc[i]){
            lol.insert({p[it].second, it});
        }
        auto it = lol.end();
        it--;
        v[it->second-1] = i;
        lol.erase(it);
    }

    neutr=n; 
    v.push_back(-INT_MAX);
    A=v;
    for (int i=0; i<n; ++i) t[sz-1+i]=i;
    update(0,0,sz);
    vector<int> ans(m,0);
    for (int q=0; q<m; ++q) {
        int l=a[q], r=b[q];
        ans[q]=query(l,r+1);
    }
    return ans;
}

Compilation message (stderr)

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