Codeforces Round #312 (Div. 2) D. Guess Your Way Out! II 贪心排序

2024-05-14 11:58

本文主要是介绍Codeforces Round #312 (Div. 2) D. Guess Your Way Out! II 贪心排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

D. Guess Your Way Out! II
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Amr bought a new video game “Guess Your Way Out! II”. The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node.

Let’s index all the nodes of the tree such that

The root is number 1
Each internal node i (i ≤ 2h - 1 - 1) will have a left child with index = 2i and a right child with index = 2i + 1
The level of a node is defined as 1 for a root, or 1 + level of parent of the node otherwise. The vertices of the level h are called leaves. The exit to the maze is located at some leaf node n, the player doesn’t know where the exit is so he has to guess his way out!

In the new version of the game the player is allowed to ask questions on the format “Does the ancestor(exit, i) node number belong to the range [L, R]?”. Here ancestor(v, i) is the ancestor of a node v that located in the level i. The game will answer with “Yes” or “No” only. The game is designed such that it doesn’t always answer correctly, and sometimes it cheats to confuse the player!.

Amr asked a lot of questions and got confused by all these answers, so he asked you to help him. Given the questions and its answers, can you identify whether the game is telling contradictory information or not? If the information is not contradictory and the exit node can be determined uniquely, output its number. If the information is not contradictory, but the exit node isn’t defined uniquely, output that the number of questions is not sufficient. Otherwise output that the information is contradictory.

Input
The first line contains two integers h, q (1 ≤ h ≤ 50, 0 ≤ q ≤ 105), the height of the tree and the number of questions respectively.

The next q lines will contain four integers each i, L, R, ans (1 ≤ i ≤ h, 2i - 1 ≤ L ≤ R ≤ 2i - 1, ), representing a question as described in the statement with its answer (ans = 1 if the answer is “Yes” and ans = 0 if the answer is “No”).

Output
If the information provided by the game is contradictory output “Game cheated!” without the quotes.

Else if you can uniquely identify the exit to the maze output its index.

Otherwise output “Data not sufficient!” without the quotes.

Sample test(s)
input
3 1
3 4 6 0
output
7
input
4 3
4 10 14 1
3 6 6 0
2 3 3 1
output
14
input
4 2
3 4 6 1
4 12 15 1
output
Data not sufficient!
input
4 2
3 4 5 1
2 3 3 1
output
Game cheated!
Note
Node u is an ancestor of node v if and only if

u is the same node as v,
u is the parent of node v,
or u is an ancestor of the parent of node v.
In the first sample test there are 4 leaf nodes 4, 5, 6, 7. The first question says that the node isn’t in the range [4, 6] so the exit is node number 7.

In the second sample test there are 8 leaf nodes. After the first question the exit is in the range [10, 14]. After the second and the third questions only node number 14 is correct. Check the picture below to fully understand.
题意就是,给出h层的完全二叉树,从上到下从左到右标号1 - 2^n,要找出出口,出口在叶子结点处。再给q个区间,表示这个区间的子结点的叶子结点中有一个是出口,或都不是出口。
这里写图片描述
我们用区间s e表示其中可能是出口,那么如果给的区间是出口,只需要求交集就可以了。得到的结果仍然是一个区间。如果,给的区间,不是出口,那就是把这部分排除啦。这样就可以会出现多个集合了。如果,就这样不断扩展,有可能最张出现q^2个集区,复杂度就会达到n^2了,这样是不行的。考虑一种贪心方法,因为只有能去掉两端的结点,这样的区间才是有效的,如果是在中间,是对结果没有影响的,如图中,2 3 对0是有影响的,在没有2 3 的情况 1号线,是对结果没有影响的,所以我们只需要通过排序,使得 2 3这样的先遇上就可以,排序后,从前往后,再从后向前,就一定保证了 2 3这种在前面,而且,不会使得结果集扩大成多集一直是单集。总的复杂度就是排序复杂度o(q * log(q));

#define N 100050
#define M 100005
#define maxn 205
#define fi first
#define se second
#define MOD 1000000000000000007
int h,q,layer[N],flag[N],pn;
ll s,e,ss,ee,l[N],r[N];
pll p[N];
void get(int layer,ll l,ll r ){ss = l << (h - layer);ee = r;FI(h - layer) ee = ee * 2 + 1;
}
int main()
{while(S2(h,q)!=EOF){s = 1ll<<(h-1);e = (1ll<<h) - 1ll;bool isRight = true;pn = 0;FI(q){S(layer[i]);cin>>l[i];cin>>r[i];S(flag[i]);if(isRight){get(layer[i],l[i],r[i]);if(flag[i]){s = max(s,ss);e = min(e,ee);if(s > e) isRight = false;}else {p[pn++] = make_pair(ss,ee);}}}if(isRight){sort(p,p+pn);FI(pn){if(p[i].first <= s && p[i].second >= s)s = p[i].second + 1;}for(int i= pn-1;i>=0;i--){if(p[i].first <= e && p[i].second >=e)e = p[i].first - 1;}}if(s > e)printf("Game cheated!\n");else if(s == e) cout<<s<<endl;else printf("Data not sufficient!\n");}return 0;
}

这篇关于Codeforces Round #312 (Div. 2) D. Guess Your Way Out! II 贪心排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/988691

相关文章

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig