Codeforces Round #600 B. Silly Mistake

Codeforces Round #600 B. Silly Mistake

最近由郑同学介绍，参加了注册并参加了Codeforces的比赛，然后就爱上了它。大半夜的比赛真的给人一种兴奋的感觉，让我再一次感受到编程的乐趣。#600是我参加的第二次CF比赛，因为A题审题错误，耗费了大量的时间，然后不知道为什么B题是无法显示的在比赛时间内时。至于C题，也能做，不过还是太菜了，直接TLE了。为了提高自己的实力，我以后会参加每一场CF，遇到有意思的题目也会记录。

题目连接：Silly Mitakes

解题思路：

标准答案很有趣，用一个数组记录每个人的三种状态：1.等待进入的 2.目前在楼内的 3.离开楼的。而我的思路应该跟大多数人一样吧，就是——边遍历边审查每个元素，遇到不符合条件的直接标记fg，这样就只执行输入操作了。

逻辑要点：

1.进入一个负数，set中找不到对应正数，-1。2.进入一个负数，set中找到对应正数，set.erase()。3.进入一个正数，set中已经有此数或该数已经出来了，-1。4.进入一个正数，set中无此正数，set.insert()。5.每次操作结束后判断当前状态，如果set为空，区间边界。6.标记元素状态也用set，因为数的范围达到1e6，而程序肯定存在极多区间，memset会超时。7.不要忘记溢出的状态。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<set>
#define f(i,a,b) for(register int i=a;i<=b;i++)
#define fd(i,a,b) for(register int i=a;i>=b;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, daylynum, x, fg, cnt;//daylynun每天的人流量,记录时*2
int ans[N];
set<int> now, zt;//now模拟楼内人流动，zt记录每个的状态
set<int>::iterator it, it2;
int main()
{
	while (cin >> n)
	{
		fg = 1;
		cnt = 1;
		daylynum = 0;
		memset(ans, 0, sizeof ans);
		f(i, 1, n)
		{
			scanf("%d", &x);
			if (fg)//无错误出现，开始审查
			{
				if (x < 0)
				{
					it = now.find(-x);//容器的优越，跟python一样直接判断有没有
					if (it == now.end())//没有对应的正数
					{
						fg = 0;
						continue;//标记报错
					}
					else {
						now.erase(it);//删除与之对应的正数
						daylynum++;
					}
				}
				else if (x > 0)
				{
					it = now.find(x);
					if (it == now.end())
					{
						it2 = zt.find(x);
						if (it2 == zt.end())//表明出于wait状态
						{
							now.insert(x);
							zt.insert(x);
						}
						else fg = 0;
					}
					else//在一个区间重复进一个正数，直接标记错误
					{
						fg = 0;
						continue;
					}
				}
				if (now.size() == 0) {
					ans[cnt++] = daylynum * 2;
					daylynum = 0;//一天结束，人流重置
					now.clear();
					zt.clear();//如果用bool数组就超时了，数的区间范围1e6，而数的数量是1e5,用memset会超时
				}
				if (i == n && now.size())//溢出
				{
					fg = 0;//细节
				}
			}
		}
		if (!fg)
			printf("-1\n");
		else
		{
			cout << cnt - 1 << endl;
			f(i, 1, cnt - 1)
				printf("%d ", ans[i]);
			printf("\n");
		}
	}
	return  0;
}