这题目乍眼一看还以为是2-sat。其实很水的,O(n)就解了。枚举每个人,假设其作为凶手。观察是否满足条件。
然后再对满足的数目分类讨论,进行求解。

 /* 156B */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = 1e5+;
int pos[maxn], neg[maxn];
vi P[maxn];
vi N[maxn];
int ans[maxn];
int st[maxn];
char s[][] = {
"Not defined",
"Truth",
"Lie"
}; int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n, m, x;
int pn = , nn = ; scanf("%d %d", &n, &m);
rep(i, , n+) {
scanf("%d", &x);
if (x > ) {
++pos[x];
P[x].pb(i);
++pn;
} else {
x = -x;
++neg[x];
N[x].pb(i);
++nn;
}
} int tmp;
vi vc; rep(i, , n+) {
// i is murder
tmp = pos[i] + nn - neg[i];
if (tmp == m)
vc.pb(i);
} int sz = SZ(vc);
if (sz == ) {
x = vc[];
rep(i, , n+)
st[i] = -;
st[x] = ;
} else {
rep(i, , n+)
st[i] = -;
rep(i, , sz)
st[vc[i]] = ;
}
rep(i, , n+) {
sz = SZ(P[i]);
if (sz && st[i]) {
x = st[i]> ? :;
rep(j, , sz)
ans[P[i][j]] = x;
}
sz = SZ(N[i]);
if (sz && st[i]) {
x = st[i]< ? :;
rep(j, , sz)
ans[N[i][j]] = x;
}
} rep(i, , n+)
puts(s[ans[i]]); #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}

最新文章

  1. checkbox的check事件
  2. uiautomator跑安卓端UI testing
  3. POJ 2838 单调队列
  4. WCF学习笔记(二):简单调用
  5. [Unity菜鸟] Mecanim 系统遇到的问题
  6. sql语句去除重复记录(多表连接的查询)
  7. 安装nodejs 后运行 npm 命令无响应处理方法
  8. [Red5]Red5之Flash流媒体服务器的安装与使用教程完整版(组图)
  9. ceph优秀博文
  10. 第三方控件netadvantage UltraWebGrid总结
  11. css3 3d初入门(一)
  12. rsync+inotify实现文件同步更新(配置)
  13. java多线程编程核心技术——第二章
  14. 初识 Runtime
  15. 运维监控-Zabbix Server 使用QQ SMTP发送邮件报警及定制报警内容
  16. Mysql5.6 自动化部署
  17. 无线渗透开启WPS功能的路由器
  18. 前端开发必备之Chrome开发者工具(上篇)
  19. 使用FastCoder写缓存单例
  20. 2-3-2 rsync+inotify备份同步数据

热门文章

  1. android 6.0特性翻译 --渣渣
  2. Android XML解析
  3. caffe源码阅读(2)-Layer
  4. PDF编译出现错误解决办法
  5. Struts2配置文件_常量属性_独立测试分析
  6. [翻译][MVC 5 + EF 6] 1:创建数据模型
  7. 管理员把我的admin权限去掉了,那么如何获得jdk zip安装呢?这篇可以帮你。
  8. WinForm TreeView 三种状态
  9. html5生成柱状图(条形图)
  10. Omnithreadlibary学习(2)-IOmniTask异步执行