#include <stdlib.h>
#include <string.h>
#include "floppy.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 17;
struct encode {
string ret;
int T[N << 2], a[N];
int n;
int best(int x, int y) {
return a[x] > a[y] ? x : y;
}
void build(int s, int l, int r) {
if (l == r) {
T[s] = l;
return;
}
int mid = l + r >> 1;
build(s << 1, l, mid);
build(s << 1 | 1, mid + 1, r);
T[s] = best(T[s << 1], T[s << 1 | 1]);
}
int get(int s, int l, int r, int from, int to) {
if (l > to || r < from) return from;
if (from <= l && r <= to) return T[s];
int mid = l + r >> 1;
return best(get(s << 1, l, mid, from, to), get(s << 1 | 1, mid + 1, r, from, to));
}
void decartes (int l, int r) {
int j = get(1, 0, n - 1, l, r);
// cout << l << " " << r << " " << j << endl;
if (j > l) {
ret.push_back('1');
decartes(l, j - 1);
}
else ret.push_back('0');
if (j < r) {
ret.push_back('1');
decartes(j + 1, r);
}
else ret.push_back('0');
}
string read_array(int subtask_id, const std::vector<int> &v) {
n = v.size();
for(int i = 0; i < n; i++) a[i] = v[i];
build(1, 0, n - 1);
decartes(0, n - 1);
return ret;
}
} encode;
void read_array(int subtask_id, const std::vector<int> &v) {
save_to_floppy(encode.read_array(subtask_id, v));
}
struct decode {
int n, cnt = 0, idnode, h[N];
int p[M + 1][N];
bool bit[N];
int dfs(int dep) {
int child0 = n, child1 = n;
if (bit[cnt++]) child0 = dfs(dep + 1);
int idx = idnode++;
if (bit[cnt++]) child1 = dfs(dep + 1);
h[idx] = dep;
// if (child0 != n) cout << child0 << " " << idx << endl;
// if (child1 != n) cout << child1 << " " << idx << endl;
p[0][child0] = idx;
p[0][child1] = idx;
return idx;
}
int lca(int u, int v) {
if (h[u] < h[v]) swap(u, v);
int delta = h[u] - h[v];
for(int j = 0; j <= M; j++) if (delta >> j & 1) u = p[j][u];
if (u == v) return u;
for(int j = M; j >= 0; j--) if (p[j][u] != p[j][v]) {
u = p[j][u];
v = p[j][v];
}
return p[0][u];
}
std::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;
for(int i = 0; i < bits.size(); i++) bit[i] = bits[i] - '0';
std::vector<int> answers(a.size());
dfs(0);
for(int j = 1; j <= M; j++) for(int i = 0; i < n; i++) p[j][i] = p[j - 1][p[j - 1][i]];
for(int i = 0; i < a.size(); i++) {
answers[i] = lca(a[i], b[i]);
// cout << answers[i] << endl;
}
return answers;
}
} decode;
vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
return decode.solve_queries(subtask_id, N, bits, a, b);
}
Compilation message
floppy.cpp: In member function 'void encode::build(int, int, int)':
floppy.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int mid = l + r >> 1;
| ~~^~~
floppy.cpp: In member function 'int encode::get(int, int, int, int, int)':
floppy.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid = l + r >> 1;
| ~~^~~
floppy.cpp: In member function 'std::vector<int> decode::solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i = 0; i < bits.size(); i++) bit[i] = bits[i] - '0';
| ~~^~~~~~~~~~~~~
floppy.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
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 time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
43836 KB |
Output is correct |
| 2 |
Correct |
5 ms |
43832 KB |
Output is correct |
| 3 |
Correct |
6 ms |
43836 KB |
Output is correct |
| 4 |
Correct |
6 ms |
44084 KB |
Output is correct |
| 5 |
Correct |
5 ms |
43844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
48428 KB |
Output is correct |
| 2 |
Correct |
22 ms |
48624 KB |
Output is correct |
| 3 |
Correct |
25 ms |
48816 KB |
Output is correct |
| 4 |
Correct |
22 ms |
48828 KB |
Output is correct |
| 5 |
Correct |
22 ms |
48524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
56564 KB |
Output is correct |
| 2 |
Correct |
87 ms |
56628 KB |
Output is correct |
| 3 |
Correct |
80 ms |
57396 KB |
Output is correct |
| 4 |
Correct |
86 ms |
58036 KB |
Output is correct |
| 5 |
Correct |
79 ms |
56640 KB |
Output is correct |
