Description

为了测试小W的物理水平，Mr.X在二维坐标系中放了N面镜子(镜子坐标绝对值不超过M)，镜子均与坐标轴成45°角，所以一共有两种类型“/”和“\”。原点不会有镜子，任意一点最多只有一面镜子。
镜子两个面都能反光，而中间不透光，例如，对于一个“/”型镜子，下方向射入的光线会被反射到右方向，左方向射入的光线会被反射到上方向。
现在有一条光线从原点沿X轴正方向射出，求走过T路程后所在位置。

Solution1

直接模拟光的走法。

复杂度：$O(T)$
得分：25

Solution2

模拟光在镜子之间的跳跃，暴力O(n)找出下一个跳到的镜子是哪个，再加上找循环节的优化，也就是记录一下以不同的方向到每个镜子的距离（从起点），每次到达一个新的镜子时，看看之前以这个角度到达过没，有则可以直接省略这个循环，即用剩下的步数模走完循环的步数。

复杂度：$O(n^2)$
得分：35

Solution3

直接模拟光的走法（跟解法1差不多），加上解法2的找循环节。

复杂度：$O(m^2)$
得分：60

Solution4

我们发现解法2的找下一个镜子这个过程很慢，于是我们优化一下，发现只要用两个数组，一个以x为第一关键字、y为第二关键字，一个以y为第一关键字，x为第二关键字，这样找上下左右四个方向的第一个镜子就直接在这两个数组里+1或-1即可。

复杂度：$O(n)$
得分：100

注意：有可能光一个镜子也没有到达。

Code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long LL;
const int N=100500;
int read(int &n)
{char ch=' ';int q=0,w=1;for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());if(ch=='-')w=-1,ch=getchar();for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int n,ans;
struct qqww{int x,y,k,s,h;}a[N];
int s[N],h[N];
LL m,x,y,k,ms;
LL f[N][4];
int TN[4][2]={{1,3},{0,2},{3,1},{2,0}};
bool PX(int q,int  w){return a[q].x<a[w].x||(a[q].x==a[w].x&&a[q].y<a[w].y);}
bool PX1(int  q,int w){return a[q].y<a[w].y||(a[q].y==a[w].y&&a[q].x<a[w].x);}
LL min(LL q,int w){return q<w?q:w;}
int main()
{freopen("mir.in","r",stdin);freopen("mir.out","w",stdout);int q,w;char ch;read(n),read(q);scanf("%lld",&m);ms=m;fo(i,1,n){read(a[i].x),read(a[i].y);ch=' ';while(ch!='/'&&ch!=92)ch=getchar();a[i].k=1;if(ch=='/')a[i].k=0;s[i]=h[i]=i;}sort(s+1,s+1+n,PX);fo(i,1,n)a[s[i]].s=i;sort(h+1,h+1+n,PX1);fo(i,1,n)a[h[i]].h=i;a[0].x=a[0].y=q+10;for(q=1;q<=n;q++)if(a[h[q]].y==0&&a[h[q]].x>0)break;if(q>n){printf("%lld 0\n",m);return 0;}q=h[q];y=0;m-=(x=min(m,a[q].x));f[q][1]=ms-m;k=TN[1][a[q].k];while(m){int K=1;if(k>1)K=-1;if(k%2==0){w=s[a[q].s+K];if(a[w].x!=a[q].x){y+=K*m;break;}int t=min(m,abs(a[w].y-a[q].y));m-=t;y+=K*t;if(f[w][k])m%=(ms-m-f[w][k]);else f[w][k]=ms-m;k=TN[k][a[w].k];q=w;}else{w=h[a[q].h+K];if(a[w].y!=a[q].y){x+=K*m;break;}int t=min(m,abs(a[w].x-a[q].x));m-=t;x+=K*t; if(f[w][k])m%=(ms-m-f[w][k]);else f[w][k]=ms-m;k=TN[k][a[w].k];q=w;}}printf("%lld %lld\n",x,y);return 0;
}