Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
27872 | liuyile | 【BJ】T3 | C++ | 通过 | 100 | 76 MS | 4328 KB | 3116 | 2024-03-31 13:21:16 |
#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define endl "\n" #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second int n,m; struct node{ int a,b,x,y; }T[100300]; double LX=0,RX,LY=0,RY;//X->x+y, Y->x-y inline bool cmp(node A,node B){ return A.a<B.a; } char c[1003000]; signed main(){ ios::sync_with_stdio(0); // freopen("bea.in","r",stdin); // freopen("bea.out","w",stdout); cin>>n>>m; RX=m;RY=m; LX=-m;LY=-m; for(int i=1;i<=n;i++){ int t,x,y; cin>>t>>x>>y; int a=t%m,b=t/m; T[i]={a,b,x,y}; } ++n; T[n]={m,-1,0,0}; sort(T+1,T+n+1,cmp); for(int i=1;i<=n;i++){ double lx=0,ly=0,rx=0,ry=0; int t=T[i].a-T[i-1].a; if(T[i].b==T[i-1].b){ int d=abs(T[i].x-T[i-1].x)+abs(T[i].y-T[i-1].y); if(d>t){ cout<<"NO"<<endl; cout.flush(); return 0; } continue; } else{ lx=(t+T[i-1].x+T[i-1].y-T[i].x-T[i].y)/-(T[i].b-T[i-1].b); rx=(t-T[i-1].x-T[i-1].y+T[i].x+T[i].y)/(T[i].b-T[i-1].b); ry=(t-T[i-1].x+T[i-1].y+T[i].x-T[i].y)/(T[i].b-T[i-1].b); ly=(t+T[i-1].x-T[i-1].y-T[i].x+T[i].y)/-(T[i].b-T[i-1].b); } if(T[i].b<T[i-1].b)swap(lx,rx),swap(ly,ry); LX=max(LX,lx),RX=min(RX,rx); LY=max(LY,ly),RY=min(RY,ry); } RX=floorl(RX); LX=ceill(LX); RY=floorl(RY); LY=ceill(LY); // cout<<LX<<" "<<RX<<" "<<LY<<" "<<RY<<endl; RX=min(RX,LX+3); RY=min(RY,LY+3); for(int A=LX;A<=RX;A++) for(int B=LY;B<=RY;B++){ if((A+B)%2)continue; int X=(A+B)/2,Y=(A-B)/2; bool p=1; // cout<<X<<" "<<Y<<endl; for(int i=1;i<=n;i++){ int db=T[i].b-T[i-1].b; int dx=T[i].x-db*X-T[i-1].x,dy=T[i].y-db*Y-T[i-1].y; int dl=T[i].a-T[i-1].a; if(dl==0&&(dx||dy)){p=0;break;} else if(abs(dx)+abs(dy)>dl){p=0;break;} else if((abs(dx)+abs(dy))%2!=dl%2){p=0;break;} int rem=dl; int now=T[i-1].a+1; if(dx>0) while(dx--)c[now++]='R',rem--; else{dx=-dx; while(dx--)c[now++]='L',rem--; } if(dy>0) while(dy--)c[now++]='U',rem--; else{dy=-dy; while(dy--)c[now++]='D',rem--; } bool p=0; while(rem--){ if(p)c[now++]='L'; else c[now++]='R'; p^=1; } } if(!p)continue; for(int i=1;i<=m;i++) cout<<c[i]; cout<<endl; cout.flush(); return 0; } cout<<"NO"<<endl; cout.flush(); return 0; }