Submission #1056924

#TimeUsernameProblemLanguageResultExecution timeMemory
1056924MighilonFloppy (RMI20_floppy)C++17
0 / 100
70 ms11520 KiB
#include <stdlib.h> #include <string.h> #include <bits/stdc++.h> using namespace std; #include "floppy.h" void read_array(int subtask_id, const std::vector<int> &v) { int n = v.size(); map<int, int> mp; for(auto i: v) mp[i]++; vector<int> a(n); int cnt = 0; for(auto& i: mp) i.second = cnt++; for(int i = 0; i < n; ++i) a[i] = mp[v[i]]; cnt--; string bits = ""; struct node{ int p, l, r; }; vector<node> tree(n + 1); tree[0] = {0, 0, 0}; for(int i = 1; i <= n; ++i){ tree[i].p = i - 1; while(tree[i].p > 0 && a[tree[i].p - 1] < a[i - 1]){ bits.push_back('0'); tree[i].p = tree[tree[i].p].p; } tree[i].l = tree[tree[i].p].r; tree[tree[i].p].r = i; tree[tree[i].l].p = i; bits.push_back('1'); } for(int i = 0; i < n; ++i){ cout << tree[i + 1].p - 1 << " "; } cout << endl; save_to_floppy(bits); } void dfs(vector<vector<int>>& adj, vector<int>& dist, int u, int d){ dist[u] = d; for(auto& v: adj[u]){ if(u == v) continue; dfs(adj, dist, v, d + 1); } }; std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) { cout << bits << endl; int n = N; struct node{ int l, p, r; }; vector<node> tree(n + 1); tree[0] = {0, 0, 0}; for(int i = 1; i < n + 1; ++i) tree[i].p = i - 1; int j = 1; for(int i = 0; i < (int)bits.size(); ++i){ if(bits[i] == '1'){ tree[j].l = tree[tree[j].p].r; tree[tree[j].p].r = j; tree[tree[j].l].p = j; j++; } else{ tree[j].p = tree[tree[j].p].p; } } int root = -1; vector<int> p(n); for(int i = 0; i < n; ++i){ p[i] = tree[i + 1].p - 1; if(p[i] == -1) p[i] = i, root = i; cout << p[i] << " "; } cout << endl; vector<vector<int>> jump(17, vector<int>(n)); for(int i = 0; i < n; i++) jump[0][i] = p[i]; for(int k = 1; k < 17; ++k) for(int i = 0; i < n; ++i) jump[k][i] = jump[k - 1][jump[k - 1][i]]; vector<int> dist(n, 0); vector<vector<int>> adj(n); for(int i = 0; i < n; ++i) adj[p[i]].push_back(i); dfs(adj, dist, root, 0); auto jump_k = [&](int a, int k){ for(int i = 0; i < 17; ++i) if(k & (1 << i)) a = jump[i][a]; return a; }; auto lca = [&](int a, int b){ if(dist[a] < dist[b]) swap(a, b); int da = dist[a]; int db = dist[b]; if(da != db){ int dif = da - db; a = jump_k(a, dif); } if(a == b) return a; for(int i = 16; i >= 0; --i){ int ja = jump_k(a, 1 << i); int jb = jump_k(b, 1 << i); if(ja != jb) a = ja, b = jb; } return jump_k(a, 1); }; vector<int> answers((int)a.size()); for(int i = 0; i < (int)a.size(); ++i){ answers[i] = lca(a[i], b[i]); cout << answers[i] << " "; } cout << endl; return answers; }

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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...