fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=300000+10;
  27.  
  28. int n;
  29. char str[MAX];
  30. int dx[]={0,1,0,-1};
  31. int dy[]={1,0,-1,0};
  32.  
  33. int pre[MAX],suf[MAX],match[MAX];
  34.  
  35. void del(int u)
  36. {
  37.     pre[suf[u]]=pre[u];
  38.     suf[pre[u]]=suf[u];
  39. }
  40.  
  41. int que[MAX],head=0,end=0;
  42. int hash[MAX];
  43.  
  44. int L[MAX],R[MAX],U[MAX],D[MAX];
  45.  
  46. struct Matrix
  47. {
  48.     int l,r,u,d;
  49.     Matrix(int a=0,int b=0,int c=0,int e=0):l(a),r(b),u(c),d(e){}
  50. };
  51.  
  52. Matrix operator + (const Matrix& a,const Matrix& b)
  53. {
  54.     return Matrix(a.l+b.l,a.r+b.r,a.u+2+b.u+b.d,a.d);
  55. }
  56.  
  57. int tot;
  58. Matrix dd[MAX];
  59.  
  60. Matrix work(int l,int r)
  61. {
  62.     int u=++tot;
  63.     Matrix ans(0,0,0,0);
  64.     if(match[l]==l+1)
  65.     {
  66.         if(str[l]=='L')
  67.             ans=Matrix(0,2,2,0);
  68.         else ans=Matrix(2,0,2,0);
  69.     }
  70.     else
  71.     {
  72.         Matrix tmp=work(l+1,match[l]-1);
  73.         if(str[l]=='L')
  74.         {
  75.             ans.d=tmp.r;
  76.             ans.u=tmp.l;
  77.             ans.r=2+tmp.u+tmp.d;
  78.             ans.l=0;
  79.         }
  80.         else
  81.         {
  82.             ans.d=tmp.l;
  83.             ans.u=tmp.r;
  84.             ans.l=3+tmp.u+tmp.d;
  85.             ans.r=0;
  86.         }
  87.     }
  88.     if(match[l]!=r)
  89.         ans=ans+work(match[l]+1,r);
  90.     dd[u]=ans;
  91.     return ans;
  92. }
  93.  
  94. int top=0;
  95. vector< pair<int,int> > ans;
  96.  
  97. void print(int x,int y)
  98. {
  99. //    cout<<x<<" "<<y<<endl;
  100. }
  101.  
  102. pair<int,int> show(int l,int r,int x,int y,int dir)//x,y灏辨槸涓婁竴涓埌杈剧殑鐐?
  103. {
  104.     ++top;
  105.     int delta=(str[l]=='P'?3:1);
  106.     int ndir=(dir+delta)%4;
  107.     if(l+1==match[l])
  108.     {
  109.         x+=dx[ndir];
  110.         y+=dy[ndir];
  111.         ans.pb(mp(x,y));
  112.         print(x,y);
  113.         x+=dx[dir];
  114.         y+=dy[dir];
  115.     }
  116.     else
  117.     {
  118.         Matrix nx=dd[top+1];
  119.         int Len=nx.d+1;
  120.         int oldx=x;
  121.         int oldy=y;
  122.         x+=dx[ndir] * Len;
  123.         y+=dy[ndir] * Len;
  124.  
  125.         ans.pb(mp(x,y));
  126.         print(x,y);
  127.  
  128.         show(l+1,match[l]-1,x,y,ndir);
  129.         x=ans[ans.size()-1].x;
  130.         y=ans[ans.size()-1].y;
  131.         if(dx[ndir])
  132.             ans[ans.size()-1].x=oldx+(nx.d+2+nx.u)*dx[ndir];
  133.         else
  134.             ans[ans.size()-1].y=oldy+(nx.d+2+nx.u)*dy[ndir];
  135.         x=ans[ans.size()-1].x;
  136.         y=ans[ans.size()-1].y;
  137.  
  138.         int p=(str[l]=='L'?nx.l:nx.r);
  139.         if(dx[dir])
  140.             x=oldx+p*dx[dir];
  141.         else y=oldy+p*dy[dir];
  142.     }
  143.     if(match[l]+1<=r)
  144.     {
  145.         int Len=dd[top+1].d+1;
  146.         x+=dx[dir]*Len;
  147.         y+=dy[dir]*Len;
  148.         ans.pb(mp(x,y));
  149.         print(x,y);
  150.         pair<int,int> tmp=show(match[l]+1,r,x,y,dir);
  151.         x=tmp.x;
  152.         y=tmp.y;
  153.     }
  154.     else
  155.     {
  156.         ans.pb(mp(x,y));
  157.         print(x,y);
  158.     }
  159.     return mp(x,y);
  160. }
  161.  
  162. int main()
  163. {
  164. #ifndef ONLINE_JUDGE
  165. //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  166. #endif
  167.     int i;
  168.     scanf("%s",str+1);
  169.     n=strlen(str+1);
  170.     int cc=0;
  171.     REP(i,1,n)
  172.     {
  173.         if(str[i]=='L')
  174.             ++cc;
  175.         else cc--;
  176.     }
  177.     if(cc!=4)
  178.     {
  179.         printf("NIE\n");
  180.         return 0;
  181.     }
  182.     int rot=0;
  183.     if(str[1]=='P')
  184.     {
  185.         REP(i,1,n)
  186.             if(str[i]=='L')
  187.             {
  188.                 rot=i;
  189.                 rotate(str+1,str+i,str+n+1);
  190.                 break;
  191.             }
  192.     }
  193.     REP(i,1,n)
  194.     {
  195.         pre[i]=i-1;
  196.         suf[i-1]=i;
  197.     }
  198.     pre[0]=n;
  199.     REP(i,1,n-1)
  200.         if(str[i]!=str[i+1])
  201.         {
  202.             que[end++]=i;
  203.             hash[i]=1;
  204.         }
  205.     while(head<end)
  206.     {
  207.         int u=que[head++];
  208.         if(suf[u] && str[suf[u]]!=str[u] && pre[suf[u]]==u && u>1)
  209.         {
  210.             match[u]=suf[u];
  211.             match[suf[u]]=u;
  212.             del(u);
  213.             del(suf[u]);
  214.             que[end++]=pre[u];
  215.         }
  216.     }
  217.     const int Len=1000000000;
  218. //    const int Len=10;
  219.     int x=0,y=0,cnt=0;
  220.     ans.pb(mp(x,y));
  221.     print(x,y);
  222.     for(i=suf[0];i;i=suf[i])
  223.     {
  224.         int r=suf[i]?(suf[i]-1):n;
  225.         int l=Len/2;
  226.         x+=dx[cnt]* l;
  227.         y+=dy[cnt]* l;
  228.         if(i+1<=r)
  229.         {
  230.             ans.pb(mp(x,y));
  231.             tot=0;
  232.             work(i+1,r);
  233.             top=0;
  234.             show(i+1,r,x,y,cnt);
  235.             if(dx[cnt])
  236.                 ans[ans.size()-1].x+=dx[cnt]*l;
  237.             else
  238.                 ans[ans.size()-1].y+=dy[cnt]*l;
  239.             x=ans[ans.size()-1].x;
  240.             y=ans[ans.size()-1].y;
  241.         }
  242.         else
  243.         {
  244.             x+=dx[cnt]*l;
  245.             y+=dy[cnt]*l;
  246.             ans.pb(mp(x,y));
  247.         }
  248.         cnt++;
  249.     }
  250.     ans[0].y=ans[ans.size()-1].y;
  251.  
  252.     map<int,int> tx,ty;
  253.     REP(i,0,(int)ans.size()-2)
  254.     {
  255.         tx[ans[i].x]=ans[i].x;
  256.         ty[ans[i].y]=ans[i].y;
  257.     }
  258.     int d=0;
  259.     for(map<int,int>::iterator it=tx.begin();it!=tx.end();++it)
  260.         it->y=d++;
  261.     d=0;
  262.     for(map<int,int>::iterator it=ty.begin();it!=ty.end();++it)
  263.         it->y=d++;
  264.     if(rot)
  265.         rotate(ans.begin(),ans.begin()+n-rot,ans.begin()+n);
  266.     REP(i,0,(int)ans.size()-2)
  267.         printf("%d %d\n",ty[ ans[i].y ],tx[ ans[i].x ] );
  268.     return 0;
  269. }
  270.  
Success #stdin #stdout 0s 19016KB
comments (?)
stdin
copy 
LLLLPPLL
stdout
copy 
0 0
3 0
3 2
2 2
2 1
1 1
1 2
0 2
https://ideone.com/EanSdz
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!