2015-2016 Petrozavodsk Winter Training Camp, Nizhny Novgorod SU Contest
B. Forcefield time limit per test 1 second memory limit per test 256 mebibytes input standard input output standard outputWhile Luke Skywalker was trying to acquire confindental data from the imperial flagship, he got into a trap. Now he is standing on the very edge of a long pipe inside the spaceship's reactor. To deal with the situation, he can move only forward. There is a stormtrooper standing at some point in front of Luke, and he have just made a shot from a blaster towards Luke. At the same moment, R2-D2 has accidentally activated the spaceship's forcefield. The forcefield generators are located on the pipe. The generators are powerful enough to change the bolt movement direction.
Each generator reflects a bolt of plasma when it comes from the front side and lets it fly through when it comes from the back. However, if the bolt comes from the front, it destroys the generator. Therefore, there are two types of generators: generators of one type face towards Luke, and generators of the other type face in the opposite direction.
After a generator is destroyed, it no longer affects the bolt. The stormtrooper's batteries are low on charge, so he cannot shoot anymore and now is lying on the bottom of the pipe so that the bolt will not hit him.
When the bolt reaches Luke, he must reflect it with the use of his lightsaber. But because of the forcefield, after being reflected, the bolt just changes direction to the opposite and continues to fly along the pipe. Luke cannot move until all the generators are destroyed. Additionally, if after destroying all the generators, the bolt flies towards Luke again, he must reflect it one more time. So, now he wonders if it's possible to destroy all the generators, and if so, how many times he will have to reflect the plasma bolt.
InputThe first line of the input contains two integers N and X, the number of generators and the distance between Luke and the stormtrooper (1 ≤ N ≤ 100 000, 1 ≤ X ≤ 109).
The next N lines contain two integers each. The i-th line contains xi, the distance between Luke and the i-th generator, and the type of the generator (1 ≤ xi ≤ 109; the type is 1 if the generator is faced towards Luke, or 0 otherwise).
The generators are given in the order of increasing distance from Luke (that is, xi < xj if i < j). The position of the stormtrooper doesn't coincide with any of the generators.
OutputPrint - 1 if it's not possible to destroy all the generators.
Otherwise, print a single integer: the number of times Luke will have to reflect the bolt of plasma.
Example input 2 3 1 1 2 1 output 3解题思路详见代码：
#include<cstdio> #include<set> using namespace std; const int maxn=1e5+5; const int INF=1e9+5; set <int> a1,a2; set<int>::iterator it; int n,x,s,p,flag; /*题目大意，一射手从x位置朝位于边缘0位置的主人公发射一颗子弹， 在这个一维的空间摆放了很多镜子，当子弹朝镜子正面飞过时， 镜子破碎，子弹反向飞，从反面则直接穿过没变化， 杀手可能在任意位置发射，发射完后他趴下 ，子弹来回飞，打不到他， 当到达主人公位置时，将子弹打回求打回的次数， 若不能将全部的镜子击碎，则输出-1 题目给出的01是以主人公为视角来说的镜子的朝向*/ int main() { while(~scanf("%d%d",&n,&x)) { for(int i=0;i<n;i++) { scanf("%d%d",&p,&s); if(s==1) a1.insert(p); else a2.insert(p); } a1.insert(INF); a1.insert(0); a2.insert(INF); a2.insert(0); int now=x; flag=0; int ans=0; while(1) { if(flag==0) { int pos = *--a2.lower_bound(now);//返回一个>=now值的迭代器位置，因为此处找一个小于now的，所以先减减用*取出来 if(pos==0)//pos==0表示主人公将子弹反弹 ans++; else //镜子将子弹反弹 a2.erase(pos);//把这个破碎的镜子去掉 now=pos; flag=1; } else { int pos = *a1.upper_bound(now); if(pos==INF) { if(a1.size()==2 && a2.size()==2) break; printf("-1\n"); //如果不是剩了俩（0、INF），就表示为空了，但是子弹已经飞出了区间 return 0; } else { a1.erase(pos); now=pos; } flag=0; } } printf("%d\n",ans); } return 0; }
