| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1181593 | CaiWinDao | Floppy (RMI20_floppy) | C++20 | 0 ms | 0 KiB |
// grok
#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
// Định nghĩa cấu trúc nút cho cây Cartesian
struct Node {
int index;
Node* left;
Node* right;
Node(int i) : index(i), left(nullptr), right(nullptr) {}
};
// Hàm tạo chuỗi dấu ngoặc cân bằng bằng cách duyệt trước
void pre_order(Node* node, string& bits) {
if (node == nullptr) return;
bits += '0'; // '('
pre_order(node->left, bits);
pre_order(node->right, bits);
bits += '1'; // ')'
}
// Xây dựng cây Cartesian từ mảng
Node* build_cartesian_tree(const vector<int>& v) {
int N = v.size();
vector<Node*> stack;
Node* root = nullptr;
for (int i = 0; i < N; i++) {
Node* node = new Node(i);
Node* last_popped = nullptr;
while (!stack.empty() && v[stack.back()->index] < v[i]) {
last_popped = stack.back();
stack.pop_back();
}
if (last_popped != nullptr) {
node->left = last_popped;
}
if (!stack.empty()) {
stack.back()->right = node;
} else {
root = node;
}
stack.push_back(node);
}
return root;
}
// Hàm xử lý lần tương tác đầu tiên: đọc mảng và lưu vào đĩa mềm
void read_array(int subtask_id, const vector<int>& v) {
Node* root = build_cartesian_tree(v);
string bits;
pre_order(root, bits);
// Lưu chuỗi bit với độ dài 2*N
save_to_floppy(2 * v.size(), bits);
// Giải phóng bộ nhớ
function<void(Node*)> delete_tree = [&](Node* node) {
if (!node) return;
delete_tree(node->left);
delete_tree(node->right);
delete node;
};
delete_tree(root);
}
// Hàm xử lý lần tương tác thứ hai: trả lời các truy vấn
vector<int> solve_queries(int subtask_id, int N, const string& bits, const vector<int>& a, const vector<int>& b) {
int len = bits.size();
// Tính toán cặp dấu ngoặc khớp nhau
vector<int> match(len, -1);
stack<int> s;
for (int i = 0; i < len; i++) {
if (bits[i] == '0') s.push(i);
else {
int start = s.top(); s.pop();
match[start] = i;
}
}
// Tính tiền tố tổng của '('
vector<int> prefix(len + 1, 0);
for (int i = 0; i < len; i++) prefix[i + 1] = prefix[i] + (bits[i] == '0' ? 1 : 0);
// Gán nhãn in-order cho từng vị trí pre-order
vector<int> pre_order_to_label(len, -1);
function<void(int, int)> assign_labels = [&](int start, int base) {
if (start >= len || bits[start] != '0') return;
int end = match[start];
int left_size = 0;
int left_end = start;
if (start + 1 < end && bits[start + 1] == '0') {
int left_start = start + 1;
left_end = match[left_start];
left_size = prefix[left_end + 1] - prefix[left_start];
assign_labels(left_start, base);
}
int label = base + left_size;
pre_order_to_label[start] = label;
int right_start = left_end + 1;
if (right_start < end && bits[right_start] == '0') {
assign_labels(right_start, base + left_size + 1);
}
};
assign_labels(0, 0);
// Xây dựng Euler tour và độ sâu
vector<pair<int, int>> tour;
function<void(int, int)> build_tour = [&](int start, int d) {
int label = pre_order_to_label[start];
tour.push_back({label, d});
int pos = start + 1;
if (pos < match[start] && bits[pos] == '0') {
int left_end = match[pos];
build_tour(pos, d + 1);
tour.push_back({label, d});
pos = left_end + 1;
}
if (pos < match[start] && bits[pos] == '0') {
build_tour(pos, d + 1);
tour.push_back({label, d});
}
};
build_tour(0, 0);
// Tính lần xuất hiện đầu tiên của mỗi nút trong Euler tour
int tour_len = tour.size();
vector<int> first_occurrence(N, -1);
for (int i = 0; i < tour_len; i++) {
int label = tour[i].first;
if (first_occurrence[label] == -1) first_occurrence[label] = i;
}
// Xây dựng bảng thưa để trả lời RMQ trên độ sâu
vector<int> log_table(tour_len + 1, 0);
for (int i = 2; i <= tour_len; i++) log_table[i] = log_table[i / 2] + 1;
int max_k = log_table[tour_len];
vector<vector<int>> sp(max_k + 1, vector<int>(tour_len, 0));
for (int i = 0; i < tour_len; i++) sp[0][i] = i;
for (int k = 1; k <= max_k; k++) {
for (int i = 0; i + (1 << k) - 1 < tour_len; i++) {
int left = sp[k - 1][i];
int right = sp[k - 1][i + (1 << (k - 1))];
sp[k][i] = (tour[left].second < tour[right].second) ? left : right;
}
}
// Hàm truy vấn chỉ số có độ sâu nhỏ nhất trong khoảng [l, r]
auto query_min = [&](int l, int r) {
int k = log_table[r - l + 1];
int left = sp[k][l];
int right = sp[k][r - (1 << k) + 1];
return (tour[left].second < tour[right].second) ? left : right;
};
// Trả lời từng truy vấn
vector<int> answers;
for (int i = 0; i < a.size(); i++) {
int p_a = first_occurrence[a[i]];
int p_b = first_occurrence[b[i]];
int l = min(p_a, p_b);
int r = max(p_a, p_b);
int min_idx = query_min(l, r);
answers.push_back(tour[min_idx].first);
}
return answers;
}