#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
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
884 KB |
Invalid run index for stub. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
3564 KB |
Invalid run index for stub. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
70 ms |
11520 KB |
Invalid run index for stub. |
| 2 |
Halted |
0 ms |
0 KB |
- |
