2008104_ac_185ms_1520k.cpp

北大大牛代码 1240道题的原代码 超级权威

# include <cstdio>
# include <algorithm>
# define MAX 50001
using namespace std;

long N;
long no[MAX];
long same[MAX];

struct node
{
	bool mark;
	long id;
	long t;
}Cows[MAX*2];

bool cmp(struct node a, struct node b)
{
	if(a.t!=b.t)
		return a.t<b.t;
	else
		if(a.id==b.id)
			return a.mark;
		else
			if(a.mark!=b.mark)
				return a.mark;
			else
				return a.id<b.id;
}

void input()
{
	int i;

	scanf("%ld",&N);
	for(i = 0; i < N; i++)
	{
		scanf("%ld%ld",&Cows[i*2].t,&Cows[i*2+1].t);
		Cows[i*2].id = Cows[i*2+1].id = i;
		Cows[i*2].mark = 1;
		Cows[i*2+1].mark = 0;
	}
}

void solve()
{
	int i;
	long p, num;

	num = p = 0;
	for(i = 0; i < 2*N; i++)
	{
		if(Cows[i].mark)
			if(p)
				no[Cows[i].id] = same[--p];
			else
				no[Cows[i].id] = ++num;
		else
			same[p++] = no[Cows[i].id];
	}
	printf("%ld\n",num);
	for(i = 0; i < N; i++)
		printf("%ld\n",no[i]);
}

int main()
{
	input();
	sort(Cows,Cows+N*2,cmp);
	solve();
	return 1;
}