Submission #857277

#	Time	Username	Problem	Language	Result	Execution time	Memory
857277		lolismek	Floppy (RMI20_floppy)	C++14	0 / 100	79 ms	16356 KiB

floppy

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

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

const int NMAX = 40000;
const int INF = 1e9 + 1;

std::vector <int> V;

std::string lin = "";

void get_cart(int l, int r){
    int mini = INF, pos = 0;
    for(int i = l; i <= r; i++){
        if(V[i] < mini){
            mini = V[i];
            pos = i;
        }
    }

    if(pos == l){
        lin += "0";
    }else{
        lin += "1";
    }

    if(pos == r){
        lin += "0";
    }else{
        lin += "1";
    }

    if(pos != l){
        get_cart(l, pos - 1);
    }
    if(pos != r){
        get_cart(pos + 1, r);
    }
}

void read_array(int subtask_id, const std::vector<int> &v){
    V = v;
    get_cart(0, (int)v.size() - 1);
    save_to_floppy(lin);
}

int ind = 0;
std::string S;

std::vector <int> adj[NMAX + 1];

int sz[NMAX + 1];
int lab[NMAX + 1];
int rlab[NMAX + 1];

const int LOG = 16;
int dp[NMAX + 1][LOG + 1];
int lvl[NMAX + 1];

int Node = 0;

int curr = 0;
int dfs(int parent){
    ++Node;

    bool l = (S[ind] == '1');
    bool r = (S[ind + 1] == '1');
    ind += 2;
    sz[Node] = 1;

    int node = Node;
    dp[node][0] = parent;
    lvl[node] = lvl[parent] + 1;

    int szl = 0;

    if(l){
        int lnode = dfs(node);
        adj[node].push_back(lnode);
        sz[node] += sz[lnode];
        szl = sz[lnode];
    }

    if(r){
        curr += sz[node];
        int rnode = dfs(node);
        curr -= sz[node];
        adj[node].push_back(rnode);
        sz[node] += sz[rnode];
    }

    lab[node] = curr + szl + 1;
    rlab[curr + szl + 1] = node;

    return node;
}

int LCA(int a, int b){
    if(lvl[a] < lvl[b]){
        std::swap(a, b);
    }

    int diff = lvl[a] - lvl[b];
    for(int i = LOG; i >= 0; i--){
        if(diff & (1 << i)){
            a = dp[a][i];
        }
    }

    if(a == b){
        return a;
    }

    for(int i = LOG; i >= 0; i--){
        if(dp[a][i] != dp[b][i]){
            a = dp[a][i];
            b = dp[b][i];
        }
    }

    return dp[a][0];
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    S = bits;

    dfs(0);

    std::vector <int> ans;

    for(int j = 1; (1 << j) <= N; j++){
        for(int i = 1; i <= N; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }

    for(int i = 0; i < (int)a.size(); i++){
        ans.push_back(lab[LCA(rlab[a[i] + 1], rlab[b[i] + 1])] - 1);
        //std::cout << ">> " << LCA(rlab[a[i] + 1], rlab[b[i] + 1]) << std::endl;
    }

    return ans;
}

/*
1 6 1
4 5 1 6 2 3
3 5
*/

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