420B


  Posted on 13 Dec 2014
implementation

Solution


#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

#define MAX_MSG_NUM 100005
#define MAX_PEOPEL_NUM 100005
#define D(x) 

struct Msg
{
	int id;
	bool on;
}msg[MAX_MSG_NUM];

int people_num, msg_num;
bool vis[MAX_PEOPEL_NUM];
bool wait[MAX_PEOPEL_NUM];
int init_num;
int ans[MAX_PEOPEL_NUM];

void input()
{
	scanf("%d%d", &people_num, &msg_num);
	for (int i = 0; i < msg_num; i++)
	{
		char st[2];
		int a;
		scanf("%s%d", st, &a);
		msg[i].on = (st[0] == '+');
		msg[i].id = a - 1;
	}
}

void make_wait()
{
	memset(vis, 0, sizeof(vis));
	memset(wait, 0, sizeof(wait));
	bool did = false;
	init_num = 0;
	for (int i = 0; i < msg_num; i++)
	{
		if (vis[msg[i].id])
		{
			continue;
		}
		if (!msg[i].on)
		{
			wait[msg[i].id] = true;
			init_num++;
			did = true;
		}
		vis[msg[i].id] = true;
	}
	if (!did)
	{
		wait[msg[0].id] = true;
	}
}

void work()
{
	int on_num = init_num;
	for (int i = 0; i < msg_num; i++)
	{
				D(printf("%d %d\n", i, on_num);)
		if (msg[i].on)
		{
			on_num++;
			if (on_num == 1 && !wait[msg[i].id])
			{
				memset(wait, 0, sizeof(wait));
			}
			continue;
		}
		on_num--;
		if (!wait[msg[i].id])
		{
			continue;
		}
		if (on_num > 0)
		{
			wait[msg[i].id] = false;
		}
	}
}

void output()
{
	int ans_num = 0;
	for (int i = 0; i < people_num; i++)
	{
		if (wait[i] || !vis[i])
		{
			ans[ans_num++] = i + 1;
			D(printf("i = %d\tans = %d\n", i, ans[ans_num - 1]);)
		}
	}
	printf("%d\n", ans_num);
	if (ans_num == 0)
		return;
	printf("%d", ans[0]);
	for (int i = 1; i < ans_num; i++)
	{
		printf(" %d", ans[i]);
	}
	puts("");
}

int main()
{
	input();
	make_wait();
	work();
	output();
	return 0;
}