CodeForces 156B Suspects(枚举)
2 seconds
256 megabytes
standard input
standard output
As Sherlock Holmes was investigating a crime, he identified n suspects. He knows for sure that exactly one of them committed the crime.
To find out which one did it, the detective lines up the suspects and numbered them from 1 to n.
After that, he asked each one: "Which one committed the crime?". Suspect number i answered either "The crime was committed by suspect
number ai",
or "Suspect number aididn't
commit the crime". Also, the suspect could say so about himself (ai = i).
Sherlock Holmes understood for sure that exactly m answers were the truth and all other answers were a lie. Now help him understand
this: which suspect lied and which one told the truth?
The first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ n)
— the total number of suspects and the number of suspects who told the truth. Next n lines contain the suspects' answers. The i-th
line contains either "+ai"
(without the quotes), if the suspect number isays that the crime was committed by suspect number ai,
or "-ai"
(without the quotes), if the suspect number i says that the suspect number ai didn't
commit the crime (ai is
an integer, 1 ≤ ai ≤ n).
It is guaranteed that at least one suspect exists, such that if he committed the crime, then exactly m people told the truth.
Print n lines. Line number i should
contain "Truth" if suspect number i has
told the truth for sure. Print "Lie" if the suspect number ilied
for sure and print "Not defined" if he could lie and could tell the truth, too, depending on who committed the crime.
1 1
+1
Truth
3 2
-1
-2
-3
Not defined
Not defined
Not defined
4 1
+2
-3
+4
-1
Lie
Not defined
Lie Not defined 枚举i是罪犯,然后看哪些人说了真话,人数等于m说明这个人可能是罪犯#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h> using namespace std;
#define MAX 100000
int n,m;
int a[MAX+5];
int b[MAX+5];
int f[MAX+5];
int tag[MAX+5];
int main()
{
scanf("%d%d",&n,&m);
int x;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&f[i]);
if(f[i]>0)
{
a[f[i]]++;
}
else
{
b[-f[i]]++;
sum++;
}
}
memset(tag,0,sizeof(tag));
int k=0;
for(int i=1;i<=n;i++)
{
if(a[i]+sum-b[i]==m)
{
tag[i]=1;
k++;
}
}
for(int i=1;i<=n;i++)
{
if(f[i]>0)
{
if(tag[f[i]]&&k==1)
printf("Truth\n");
else if(!tag[f[i]])
printf("Lie\n");
else
printf("Not defined\n");
}
else
{
if(!tag[-f[i]])
printf("Truth\n");
else if(tag[-f[i]]&&k==1)
printf("Lie\n");
else
printf("Not defined\n");
}
}
return 0;
}
最新文章
- 里面的div怎么撑开外面的div,让高度自适应
- yii的csv导出
- SqlSever基础 select cast 将一个int类型数据转换为char
- postgresql 分区表创建及测试
- MyBatis学习系列二——增删改查
- Oracle ->;>; 查看分区表的每个分区的数据行分布情况
- ORA-00054
- Syntax highlighter for CKEditor
- phpcms v9后台多表查询分页代码
- HtmlParser基础教程
- 项目适配iOS9遇到的一些问题及解决办法
- IO流数据读写总结
- HTML5 语义元素、迁移、样式指南和代码约定
- Mac之OS系统下搭建JavaEE环境 <;四>; 之IntelliJ IDEA 的内存优化
- 波涛1202wm8833 lihomme/历织造 2013秋装全新男装夹克 整身年龄外套潮流立领男士休闲外套薄_9才号
- <;pre>;标签:\r\n换行符的保留
- Broken Keyboard (a.k.a. Beiju Text) 思路
- 关于阿里云和ucloud云服务器负载均衡器slb和ulb会话保持的配置
- jquery 中的回调函数,回调函数(callback)是什么?
- JS-cookie封装