Submission #855976

#	Time	Username	Problem	Language	Result	Execution time	Memory
855976		mraron	Floppy (RMI20_floppy)	C++17	100 / 100	555 ms	67932 KiB

floppy

#include <stdlib.h>
#include "floppy.h"

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

#define sz(x) (int)(x).size()
#define xx first
#define yy second

deque<char> merge(deque<char>& a, deque<char>& b) {
    if(sz(b)>sz(a)) {
        while(!a.empty()) {b.push_front(a.back()); a.pop_back();}
        return b;
    }else {
        while(!b.empty()) {a.push_back(b.front()); b.pop_front();}
        return a;
    }
}

deque<char> construct(int L, int R, set<pair<int,int>>& ord, const vector<int>& t) {
    if(L>R) return {};
    int mid=(L+R)/2;
    int biggestPos=prev(ord.end())->yy;
    ord.erase({t[biggestPos], biggestPos});
    
    deque<char> a,b;
    if(biggestPos<=mid) {
        for(int i=L;i<biggestPos;++i) {
            ord.erase({t[i], i});
        }
    
        b=construct(biggestPos+1, R, ord, t);
        for(int i=L;i<biggestPos;++i) {
            ord.insert({t[i], i});
        }
        a=construct(L, biggestPos-1, ord, t);
    }else {
        for(int i=biggestPos+1;i<=R;++i) {
            ord.erase({t[i], i});
        }
        
        a=construct(L, biggestPos-1, ord, t);
        for(int i=biggestPos+1;i<=R;++i) {
            ord.insert({t[i], i});
        }
        b=construct(biggestPos+1, R, ord, t);
    }

    deque<char> res;
    if(a.empty()) res.push_back('0'); else res.push_back('1');
    if(b.empty()) res.push_back('0'); else res.push_back('1');
    
    a=merge(a,b);
    return merge(res, a);
}

void read_array(int subtask_id, const std::vector<int> &v) {
    set<pair<int,int>> ord;
    for(int i=0;i<sz(v);++i) ord.insert({v[i], i});
    deque<char> b=construct(0, sz(v)-1, ord, v);
    string bits;
    for(auto i:b) bits.push_back(i);
    save_to_floppy(bits);
}



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 ind=0;
    vector<int> par(N, -1), lvl(N, 0);
    function<pair<int,int>(int, int)> dfs=[&](int pos, int l) -> pair<int,int> {
        int st=pos+2, bal=-1, x, jobb=-1;
        if(bits[pos]=='1') {
            auto res=dfs(st, l+1);
            st=res.xx;
            bal=res.yy;
        }
        x=ind++;
        lvl[x]=l;
        //~ cerr<<x<<" "<<pos<<" "<<l<<" "<<bits<<"\n";
        if(bits[pos+1]=='1') {
            auto res=dfs(st, l+1);
            st=res.xx;
            jobb=res.yy;
        }
        
        if(bal!=-1) par[bal]=x;
        if(jobb!=-1) par[jobb]=x;
        return {st, x};
    };
    
    dfs(0, 0);
    //~ for(auto i:par) cerr<<i<<" ";
    //~ cerr<<"\n";
    
    vector<array<int,17>> dp(N);
    for(int i=0;i<N;++i) dp[i][0]=par[i];
    for(int j=1;j<17;++j) {
        for(int i=0;i<N;++i) {
            dp[i][j]=(dp[i][j-1]==-1?-1:dp[dp[i][j-1]][j-1]);
        }
    }

    vector<int> ans(sz(a));
    for(int i=0;i<sz(a);++i) {
        int x=a[i], y=b[i];
        if(lvl[x]>lvl[y]) swap(x,y);
        for(int j=16;j>=0;j--) {
            int q=dp[y][j];
            if(q!=-1 && lvl[q]>=lvl[x]) y=q;
        }
        if(x==y) {
            ans[i]=x;
            continue ;
        }
        for(int j=16;j>=0;j--) {
            int p=dp[x][j], q=dp[y][j];
            if(p!=q) x=p, y=q;
        }
        ans[i]=dp[x][0];
    }
    
    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: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72