#include #define DEAD false #define ALIVE true // 'Natural count' is the name of the node when all the nodes in the tree is // alive. xxx_num denotes the count as the question described. // SEE ALSO BRANCH 04_02 WITH A CORRECT IMPLEMENTATION int ans[200] = {0}; long long dead_nodes_num[105] = {0}; int total_dead_nodes = 0; long long target_nodes_num[105] = {0}; int total_target_nodes = 0; struct SeveralContinuedDeadNode { bool status; long long length; // Caution that when status == dead and length == 1, the node itself is alive. }; struct SearchResult { int next_ans_pos; // pos in the ans[] array. long long count_in_father_line; // natural count. }; SearchResult find_node(long long target, long long start_num, int next_dead_node_num_ptr, SeveralContinuedDeadNode *upper_line, long long upper_line_segment_count, int layer) { long long spawned_node_max_num = start_num - 1; long long segment_count = upper_line_segment_count; SeveralContinuedDeadNode current_line_node[200] = {0}; long long current_line_len = 0; bool all_dead = true; // Spawing all the nodes in current line for (int upper_line_iter = 0; upper_line_iter < upper_line_segment_count; upper_line_iter++) { if (upper_line[upper_line_iter].status == DEAD) { current_line_node[current_line_len] = upper_line[upper_line_iter]; current_line_node[current_line_len].length *= 2; current_line_len++; } else { all_dead = false; long long total_spawned_after = spawned_node_max_num + upper_line[upper_line_iter].length * 2; while (dead_nodes_num[next_dead_node_num_ptr] <= total_spawned_after && next_dead_node_num_ptr < total_dead_nodes) { if (dead_nodes_num[next_dead_node_num_ptr] - spawned_node_max_num > 1) { current_line_node[current_line_len] = SeveralContinuedDeadNode{ ALIVE, dead_nodes_num[next_dead_node_num_ptr] - spawned_node_max_num - 1}; current_line_len++; // things before this new dead node } current_line_node[current_line_len] = SeveralContinuedDeadNode{DEAD, 1}; // this new dead node current_line_len++; spawned_node_max_num = dead_nodes_num[next_dead_node_num_ptr]; // we now spawned to // this dead node. next_dead_node_num_ptr++; } if (spawned_node_max_num < total_spawned_after) { current_line_node[current_line_len] = SeveralContinuedDeadNode{ALIVE, total_spawned_after - spawned_node_max_num}; current_line_len++; } spawned_node_max_num = total_spawned_after; } } if (all_dead) { return SearchResult{1, -1}; } if (target <= spawned_node_max_num) { ans[0] = target; long long natural_pos = -1, num = start_num - 1; for (int i = 0; i < current_line_len; i++) { if (current_line_node[i].status == DEAD) { natural_pos += current_line_node[i].length; num += (current_line_node[i].length == 1); if (num == target) { return SearchResult{1, natural_pos / 2}; } continue; } // Now deal with alive nodes if (num + current_line_node[i].length < target) { natural_pos += current_line_node[i].length; num += current_line_node[i].length; } else { // if we made it here, then the target > num + current_line_node[i].length return SearchResult{1, (natural_pos + target - num) / 2}; } } return SearchResult{1, -1}; } else { SearchResult current_line_pos = find_node(target, spawned_node_max_num + 1, next_dead_node_num_ptr, current_line_node, current_line_len, layer + 1); if (current_line_pos.count_in_father_line < 0) { // The path does not exist. return SearchResult{1, -1}; } long long natural_count = -1, num = start_num - 1; for (int i = 0; i < current_line_len; i++) { natural_count += current_line_node[i].length; if (current_line_node[i].status == ALIVE || current_line_node[i].length == 1) { num += current_line_node[i].length; } if (natural_count >= current_line_pos.count_in_father_line) { num -= natural_count - current_line_pos.count_in_father_line; ans[current_line_pos.next_ans_pos++] = num; break; } } return SearchResult{current_line_pos.next_ans_pos, current_line_pos.count_in_father_line / 2}; } } int main() { scanf("%d %d", &total_dead_nodes, &total_target_nodes); for (int i = 0; i < total_dead_nodes; i++) { scanf("%lld", &dead_nodes_num[i]); } for (int i = 0; i < total_target_nodes; i++) { scanf("%lld", &target_nodes_num[i]); } if (dead_nodes_num[0] == 1) { for (int i = 0; i < total_target_nodes; i++) { if (target_nodes_num[i] == 1) { printf("1\n"); continue; } else { printf("0\n"); } } return 0; } else { SeveralContinuedDeadNode firstline = SeveralContinuedDeadNode{ALIVE, 1}; for (int i = 0; i < total_target_nodes; i++) { SearchResult result = find_node(target_nodes_num[i], 2, 0, &firstline, 1, 2); if (result.count_in_father_line == -1) { printf("0\n"); } else { printf("1 "); for (int j = result.next_ans_pos - 1; j >= 0; j--) { printf("%lld ", ans[j]); } printf("\n"); } } } return 0; }