4955小球装箱游戏

4955   小球装箱游戏

题目描述

乐乐小朋友正在玩一个小球装箱的游戏。现在有N个小球(编号为1到N),每个小球有一种颜色(红色或者绿色),并且每个小球上都标有一个数字。现在有两个不同的球箱 A和B,乐乐想把这些球放进这两个球箱里面,并且保证:
1、每个球箱中球的数量要一样多。
2、球箱 A 中的任意一个球上的数字不小于球箱 B中任意一个球上的数字。
3、如果红色小球和绿色小球上的数字相同时,红色小球优先放入球箱A。
装箱完成后,乐乐想知道 A、B 两个球箱中红色小球和绿色小球各有多少个。由于球的数量比较多,请你编程计算一下吧。

输入格式:

输入共 N+1行。第1行是一个整数N(2≤N≤100000),表示小球的总数。
接下来 N 行,第 i+1 行两个整数 Mi(1≤Mi<20000)和Pi(Pi为0或者 1),其中Mi 表示第i个小球上面的数字,Pi表示第i个小球的颜色,0 表示小球是红色,1表示小球是绿色。数据保证球的个数 N为偶数,

输出格式:

第1行两个整数,分别表示球箱A 中红色小球和绿色小球的数量。
第2行两个整数,分别表示球箱B中红色小球和绿色小球的数量,
输入样例 复制
8
2 1
2 0
2 0
4 1
2 0
5 1
8 1
1 1
输出样例 复制
1 3
2 2

说明

对于 60%的数据,I≤N≤10000,1≤Mi≤10000,且保证各小球上标有的数字都不一样。
对于100%的数据,1≤N≤100000,1≤Mi≤20000。
1
1
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型
难        度