Submission #954274

#	Time	Username	Problem	Language	Result	Execution time	Memory
954274		TAhmed33	Floppy (RMI20_floppy)	C++17	0 / 100	26 ms	9052 KiB

floppy

#include <bits/stdc++.h>
using namespace std;
#include "floppy.h"
const int MAXN = 4e4 + 25;
int a[MAXN], n;
int nxt[MAXN], prv[MAXN];
vector <int> adj[MAXN];
string ret;
void dfs (int pos) {
    sort(adj[pos].begin(), adj[pos].end());
    if (adj[pos].empty()) {
        ret += "00";
        return;
    }
    if (adj[pos].size() == 1) {
        if (adj[pos][0] > pos) {
            ret += "01";
        } else {
            ret += "10";
        }
        dfs(adj[pos][0]);
    } else {
        ret += "11";
        dfs(adj[pos][0]);
        dfs(adj[pos][1]);
    }
}
void read_array(int subtask_id, const std::vector<int> &v) {
    n = v.size();
    for (int i = 1; i <= n; i++) a[i] = v[i - 1];
    stack <int> cur; cur.push(1);
    for (int i = 2; i <= n; i++) {
        while (!cur.empty() && a[cur.top()] < a[i]) {
            nxt[cur.top()] = i;
            cur.pop();
        }
        cur.push(i);
    }
    while (!cur.empty()) {
        nxt[cur.top()] = -1;
        cur.pop();
    }
    cur.push(n);
    for (int i = n - 1; i >= 1; i--) {
        while (!cur.empty() && a[cur.top()] < a[i]) {
            prv[cur.top()] = i;
            cur.pop();
        }
        cur.push(i);
    }
    while (!cur.empty()) {
        prv[cur.top()] = -1;
        cur.pop();
    }  assert(0);

    int root = -1;
    for (int i = 1; i <= n; i++) {
        if (nxt[i] == -1 && prv[i] == -1) {
            root = i;
            continue;
        }
        if (nxt[i] == -1) {
            adj[prv[i]].push_back(i);
        } 
        if (prv[i] == -1) {
            adj[nxt[i]].push_back(i);
        }
        if (a[nxt[i]] < a[prv[i]]) {
            adj[nxt[i]].push_back(i);
        } else {
            adj[prv[i]].push_back(i);
        }
    }
    dfs(root);
    assert((int)ret.size() == 2 * n);
    save_to_floppy(ret);
}
int deg[MAXN];
vector <int> inorder;
int L[MAXN], R[MAXN];
int idx[MAXN];
int dp[20][MAXN], dep[MAXN];
void dfs2 (int pos) {
    if (L[pos] != -1) {
        dp[0][L[pos]] = pos;
        dep[L[pos]] = 1 + dep[pos];
        dfs2(L[pos]);
    }
    inorder.push_back(pos);
    if (R[pos] != -1) {
        dp[0][R[pos]] = pos;
        dep[R[pos]] = 1 + dep[pos];
        dfs2(R[pos]);
    }
}
int jump (int a, int b) {
    for (int i = 19; i >= 0; i--) {
        if (b & (1 << i)) {
            a = dp[i][a];
        }
    }
    return a;
}
int lca (int a, int b) {
    if (dep[a] > dep[b]) swap(a, b);
    b = jump(b, dep[b] - dep[a]);
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) {
        int x = dp[i][a], y = dp[i][b];
        if (x && y && x != y) {
            a = x, b = y;
        }
    }
    return dp[0][a];
}
vector <int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    n = N;  
    vector <int> ret;
    stack <int> cur;
    for (int i = 1; i <= n; i++) {
        deg[i] = (bits[2 * i - 2] == '1') + (bits[2 * i - 1] == '1');
    }
    cur.push(1); 
    for (int i = 2; i <= n; i++) {
        while (!cur.empty()) {
           if (deg[cur.top()] == 0) cur.pop();
           else {
                adj[cur.top()].push_back(i);
                deg[cur.top()]--;
                break;
           } 
        }
        cur.push(i);
    }
    for (int i = 1; i <= n; i++) {
        L[i] = R[i] = -1;
        sort(adj[i].begin(), adj[i].end());
        bool f = 0;
        if (bits[2 * i - 2] == '1') {
            L[i] = adj[i][0]; f = 1;
        }
        if (bits[2 * i - 1] == '1') {
            R[i] = (f ? adj[i][1] : adj[i][0]);
        }
    }
    inorder.push_back(0);
    dfs2(1);
    for (int i = 1; i <= n; i++) {
        idx[i] = inorder[i];
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
    for (int i = 0; i < (int)a.size(); i++) {
        //cout << idx[a[i] + 1] << " " << idx[b[i] + 1] << ": " << lca(idx[a[i] + 1], idx[b[i] + 1]) << '\n'; 
        ret.push_back(inorder[lca(idx[a[i] + 1], idx[b[i] + 1])] - 1);
    }
    return ret;
}

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