API tools faq
paste
cielavenir

icpc2007dA Pxem optimized (253bytes)

cielavenir
Apr 23rd, 2012
157
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.65 KB | None | 0 0
raw download clone embed print report
  1. //nuko admitted there is specification bug that it doesn't have "swap".
  2. //#define EXTENDED
  3.  
  4. #define PUSHINT0  "00.-"
  5. #define PUSHINT1  "01.-"
  6. #define PUSHINT2  "02.-"
  7. //#define PUSHINT1000  "ak.-d.!"
  8. #define PUSHINTL  "zz.!"
  9. //#define PUTSPACE  "0P.-.o"
  10. //#define PUTCOLON  "0j.-.o"
  11. #define PUTLF     "ak.-.o"
  12. #define INCREMENT PUSHINT1".+"
  13. #define DECREMENT PUSHINT1".-"
  14. #define PXEM      ".pxem"
  15.  
  16. //after using these subroutines, temporary area will be overwritten.
  17. #define ROTATEL   ".t.v.m.v"
  18. #define ROTATER   ".v.t.v.m"
  19. #define PEEKT     ".c.t"
  20. #define PEEKB     ".v.c.t.v"
  21. //#define POPB      ".v.t.v"
  22.  
  23. #ifdef EXTENDED
  24. //._.c.w.c.v00.-zz.!00.-.v.c.w._.c.t.v.c.m.h.x.s.m00.a.m.h.t.v.m.v.t.c.m.h.y.s.m00.a.m.h.t.v.m.v.+.v.t.v.m.v.t.v.m.v.s01.-.-.c.a.s02.-.-.t.-.-.m.$.nak.-.o._.c.a.s.pxem
  25. char *FILENAME=
  26. "._.c.w" //n while n
  27.     ".c" //i,n
  28.     ".v" //n,i
  29.     PUSHINT0 PUSHINTL PUSHINT0 //max,min,sum,n,i
  30.     ".v.c.w"       //i,n,sum,min,max while i
  31.         "._" PEEKT //x,i,n,sum,min,max t==x
  32.         ".v"       //max,min,sum,n,i,x t==x
  33.         ".c.m.h"
  34.  
  35.         //max,x,max,min,sum,n,i,x t==x
  36.         ".x"       // while max < x
  37.         ".s.m"
  38.         "00.a"
  39.         //max,min,sum,n,i,x t==x
  40.         ".m.h"     //max,x,min,sum,n,i,x
  41.         ROTATEL    //x,min,sum,n,i,x,max
  42.         ".t.c.m.h"
  43.  
  44.         //min,x,min,sum,n,i,x,max t==x
  45.         ".y"       // while min > x
  46.         ".s.m"
  47.         "00.a"
  48.  
  49.         //min,sum,n,i,x,max t==x
  50.         ".m.h"     //min,x,sum,n,i,x,max
  51.         ROTATEL    //x,sum,n,i,x,max,min
  52.         ".+"       //sum,n,i,x,max,min
  53.         ROTATER ROTATER ".v.s" //i,n,sum,min,max
  54.     DECREMENT".c.a"
  55.  
  56.     ".s" PUSHINT2 ".-.t" //sum,min,max t==n-2
  57.     ".-.-.m.$.n"PUTLF
  58. "._.c.a.s"PXEM;
  59. char *CONTENT="";
  60. #else
  61. //._.c.w.c.v00.-zz.!00.-.v.c.w._.c.t.v.t.v.m.v.e.t.v.m.v.e.v.t.v.m.v.t.v.m.v.c.t.v.x.s.m00.a.t.v.m.v.e.t.v.m.v.t.v.m.v.e.t.v.m.v.e.v.t.v.m.v.t.v.m.v.c.t.v.y.s.m00.a.t.v.m.v.e.+.v.t.v.m.v.t.v.m.s.v.t.v.m.v.s01.-.-.c.a.s02.-.-.t.-.-.m.$.nak.-.o._.c.a.s.pxem
  62. char *FILENAME=
  63. "._.c.w" //n while n
  64.     ".c" //i,n
  65.     ".v" //n,i
  66.     PUSHINT0 PUSHINTL PUSHINT0 //max,min,sum,n,i
  67.     ".v.c.w"       //i,n,sum,min,max while i
  68.         "._" PEEKT //x,i,n,sum,min,max t==x
  69.         ".v"       //max,min,sum,n,i,x t==x
  70.         ROTATEL    //min,sum,n,i,x,max
  71.         ".e"       //x,min,sum,n,i,x,max
  72.         ROTATEL    //min,sum,n,i,x,max,x
  73.         ".e"       //max,min,sum,n,i,x,max,x
  74.         ROTATER ROTATER PEEKB
  75.  
  76.         //max,x,max,min,sum,n,i,x t==x
  77.         ".x"       // while max < x
  78.         ".s.m"     // max<-t(==x)
  79.         "00.a"     // break
  80.         //max,min,sum,n,i,x t==x
  81.         ROTATEL    //min,sum,n,i,x,max
  82.         ".e"       //x,min,sum,n,i,x,max
  83.         ROTATEL ROTATEL //sum,n,i,x,max,x,min
  84.         ".e"       //x,sum,n,i,x,max,x,min
  85.         ROTATEL    //sum,n,i,x,max,x,min,x
  86.         ".e"       //min,sum,n,i,x,max,x,min,x
  87.         ROTATER ROTATER PEEKB
  88.  
  89.         //min,x,min,sum,n,i,x,max,x t==x
  90.         ".y"       // while min > x
  91.         ".s.m"     // min<-t(==x)
  92.         "00.a"     // break
  93.  
  94.         //min,sum,n,i,x,max,x t==x
  95.         ROTATEL    //sum,n,i,x,max,x,min
  96.         ".e"       //x,sum,n,i,x,max,x,min
  97.         ".+"       //sum,n,i,x,max,x,min
  98.         ROTATER ROTATER ".s" ROTATER ".v.s" //i,n,sum,min,max
  99.     DECREMENT".c.a"
  100.  
  101.     ".s" PUSHINT2 ".-.t" //sum,min,max t==n-2
  102.     ".-.-.m.$.n"PUTLF
  103. "._.c.a.s"PXEM;
  104. char *CONTENT=".v.s.t.s.s.s.s.s.s.m"; //return second-last element
  105. #endif
  106.  
  107. // http://cfs.maxn.jp/neta/pxem.php
  108. #include <cstdio>
  109. #include <string>
  110. #include <cstring>
  111. #include <stack>
  112. #include <queue>
  113. #include <ctime>
  114. #include <cstdlib>
  115. #include <cmath>
  116. using namespace std;
  117. class Pxem{
  118.     private:
  119.         stack<int>  pStack;     // stack
  120.         char        *fName;     // file name
  121.         char        *fCont;     // file contents
  122.         int     temp;       // temporary area
  123.         bool        used;       // used temp?
  124.         void    print();        // print stack
  125.         bool    out();          // output
  126.         void    numOut();       // output(number)
  127.         void    input();        // input
  128.         void    numInput();     // number input
  129.         void    copy();         // x,y,z -> x,x,y,z
  130.         void    throwAway();        // x,y,z -> y,z
  131.         void    inverse();      // x,y,z -> z,y,x
  132.         void    fileRead();     // input from file contents
  133.         void    emu();          // run pxem using file contents
  134.         void    getRand();      // create random number from stack[0]
  135.         void    toTemp();       // temp = stack[0];
  136.         void    fromTemp();     // if(used) stack.push(temp);
  137.         void    addition();     // x,y,z -> (x+y),z
  138.         void    subtraction();      // x,y,z -> abs(x-y),z
  139.         void    multiplication();   // x,y,z -> (x*y),z
  140.         void    getQuotient();      // x,y,z -> (x>y?int(x/y):int(y/x)),z
  141.         void    getSurplus();       // x,y,z -> (x>y?int(x%y):int(y%x)),z
  142.         void    addStr(char*);      // addStr("ab"); -> pStack.push(98);pStack.push(97);
  143.  
  144.         void    getXor();   // x,y,z -> x^y,z
  145.         void    excHange();     // x,y,z -> y,x,z
  146.     public:
  147.         Pxem(char*,char*);          // constructor from main()
  148.         Pxem(char*,char*,stack<int>);       // constructor from Pxem
  149.         void    run();              // run pxem
  150.         stack<int>  getStack() const;   // get stack
  151. };
  152. Pxem::Pxem(char *f, char *g):fName(f),fCont(g){srand((unsigned)time(NULL));}
  153. Pxem::Pxem(char *f, char *g,stack<int> hoge):fName(f),fCont(g){
  154.     srand((unsigned)time(NULL));
  155.     stack<int>fuga;
  156.     while(!hoge.empty()){
  157.         fuga.push((int)hoge.top());
  158.         hoge.pop();
  159.     }
  160.     while(!fuga.empty()){
  161.         pStack.push(fuga.top());
  162.         hoge.push(fuga.top());
  163.         fuga.pop();
  164.     }
  165. }
  166. void Pxem::run(){
  167.     long ps     = 0;
  168.     long slen   = strlen(fName);
  169.     string buf;
  170.     while(ps<slen){
  171.         if(fName[ps]=='.'&&ps+1<slen){
  172.             int cnt;
  173.             int ccp;
  174.             switch(fName[++ps]){
  175.                 case 'p':
  176.                 case 'P':
  177.                     // print stack
  178.                     addStr((char*)buf.c_str());
  179.                     buf = "";
  180.                     print();
  181.                     break;
  182.                 case 'o':
  183.                 case 'O':
  184.                     // output
  185.                     addStr((char*)buf.c_str());
  186.                     buf = "";
  187.                     out();
  188.                     break;
  189.                 case 'n':
  190.                 case 'N':
  191.                     // output(number)
  192.                     addStr((char*)buf.c_str());
  193.                     buf = "";
  194.                     numOut();
  195.                     break;
  196.                 case 'i':
  197.                 case 'I':
  198.                     // input
  199.                     addStr((char*)buf.c_str());
  200.                     buf = "";
  201.                     input();
  202.                     break;
  203.                 case '_':
  204.                     // input(number)
  205.                     addStr((char*)buf.c_str());
  206.                     buf = "";
  207.                     numInput();
  208.                     break;
  209.                 case 'c':
  210.                 case 'C':
  211.                     // x,y,z -> x,x,y,z
  212.                     addStr((char*)buf.c_str());
  213.                     buf = "";
  214.                     copy();
  215.                     break;
  216.                 case 's':
  217.                 case 'S':
  218.                     // x,y,z -> x,y
  219.                     addStr((char*)buf.c_str());
  220.                     buf = "";
  221.                     throwAway();
  222.                     break;
  223.                 case 'v':
  224.                 case 'V':
  225.                     // x,y,z -> z,y,x
  226.                     addStr((char*)buf.c_str());
  227.                     buf = "";
  228.                     inverse();
  229.                     break;
  230.                 case 'f':
  231.                 case 'F':
  232.                     // input from file contents
  233.                     addStr((char*)buf.c_str());
  234.                     buf = "";
  235.                     fileRead();
  236.                     break;
  237.                 case 'e':
  238.                 case 'E':
  239.                     // run pxem using file contents
  240.                     addStr((char*)buf.c_str());
  241.                     buf = "";
  242.                     emu();
  243.                     break;
  244.                 case 'r':
  245.                 case 'R':
  246.                     // create random number from stack[0]
  247.                     addStr((char*)buf.c_str());
  248.                     buf = "";
  249.                     getRand();
  250.                     break;
  251.                 case 'w':
  252.                 case 'W':
  253.                     addStr((char*)buf.c_str());
  254.                     buf="";
  255.                     if(!pStack.empty()){
  256.                         cnt=pStack.top();
  257.                         pStack.pop();
  258.                         if(cnt==0){
  259.                             ps++;
  260.                             cnt=1;
  261.                             while(cnt){
  262.                                 if(fName[ps]=='.'){
  263.                                     switch(fName[++ps]){
  264.                                         case 'w':
  265.                                         case 'W':
  266.                                         case 'x':
  267.                                         case 'X':
  268.                                         case 'y':
  269.                                         case 'Y':
  270.                                         case 'z':
  271.                                         case 'Z':
  272.                                             cnt++;
  273.                                             break;
  274.                                         case 'a':
  275.                                         case 'A':
  276.                                             cnt--;
  277.                                             break;
  278.                                     }
  279.                                 }
  280.                                 ps++;
  281.                             }
  282.                             ps--;
  283.                         }
  284.                     }
  285.                     break;
  286.                 case 'x':
  287.                 case 'X':
  288.                     addStr((char*)buf.c_str());
  289.                     buf="";
  290.                     if(pStack.size()>1){
  291.                         cnt=pStack.top();
  292.                         pStack.pop();
  293.                         ccp=pStack.top();
  294.                         pStack.pop();
  295.                         if(cnt>=ccp){
  296.                             ps++;
  297.                             cnt=1;
  298.                             while(cnt){
  299.                                 if(fName[ps]=='.'){
  300.                                     switch(fName[++ps]){
  301.                                         case 'w':
  302.                                         case 'W':
  303.                                         case 'x':
  304.                                         case 'X':
  305.                                         case 'y':
  306.                                         case 'Y':
  307.                                         case 'z':
  308.                                         case 'Z':
  309.                                             cnt++;
  310.                                             break;
  311.                                         case 'a':
  312.                                         case 'A':
  313.                                             cnt--;
  314.                                             break;
  315.                                     }
  316.                                 }
  317.                                 ps++;
  318.                             }
  319.                             ps--;
  320.                         }
  321.                     }
  322.                     break;
  323.                 case 'y':
  324.                 case 'Y':
  325.                     addStr((char*)buf.c_str());
  326.                     buf="";
  327.                     if(pStack.size()>1){
  328.                         cnt=pStack.top();
  329.                         pStack.pop();
  330.                         ccp=pStack.top();
  331.                         pStack.pop();
  332.                         if(cnt<=ccp){
  333.                             ps++;
  334.                             cnt=1;
  335.                             while(cnt){
  336.                                 if(fName[ps]=='.'){
  337.                                     switch(fName[++ps]){
  338.                                         case 'w':
  339.                                         case 'W':
  340.                                         case 'x':
  341.                                         case 'X':
  342.                                         case 'y':
  343.                                         case 'Y':
  344.                                         case 'z':
  345.                                         case 'Z':
  346.                                             cnt++;
  347.                                             break;
  348.                                         case 'a':
  349.                                         case 'A':
  350.                                             cnt--;
  351.                                             break;
  352.                                     }
  353.                                 }
  354.                                 ps++;
  355.                             }
  356.                             ps--;
  357.                         }
  358.                     }
  359.                     break;
  360.                 case 'z':
  361.                 case 'Z':
  362.                     addStr((char*)buf.c_str());
  363.                     buf="";
  364.                     if(pStack.size()>1){
  365.                         cnt=pStack.top();
  366.                         pStack.pop();
  367.                         ccp=pStack.top();
  368.                         pStack.pop();
  369.                         if(cnt==ccp){
  370.                             ps++;
  371.                             cnt=1;
  372.                             while(cnt){
  373.                                 if(fName[ps]=='.'){
  374.                                     switch(fName[++ps]){
  375.                                         case 'w':
  376.                                         case 'W':
  377.                                         case 'x':
  378.                                         case 'X':
  379.                                         case 'y':
  380.                                         case 'Y':
  381.                                         case 'z':
  382.                                         case 'Z':
  383.                                             cnt++;
  384.                                             break;
  385.                                         case 'a':
  386.                                         case 'A':
  387.                                             cnt--;
  388.                                             break;
  389.                                     }
  390.                                 }
  391.                                 ps++;
  392.                             }
  393.                             ps--;
  394.                         }
  395.                     }
  396.                     break;
  397.                 case 'a':
  398.                 case 'A':
  399.                     addStr((char*)buf.c_str());
  400.                     buf="";
  401.                     ps-=2;
  402.                     cnt=-1;
  403.                     while(cnt){
  404.                         if(fName[ps]=='.'){
  405.                             switch(fName[ps+1]){
  406.                                 case 'w':
  407.                                 case 'W':
  408.                                 case 'x':
  409.                                 case 'X':
  410.                                 case 'y':
  411.                                 case 'Y':
  412.                                 case 'z':
  413.                                 case 'Z':
  414.                                     cnt++;
  415.                                     break;
  416.                                 case 'a':
  417.                                 case 'A':
  418.                                     cnt--;
  419.                                     break;
  420.                             }
  421.                         }
  422.                         ps--;
  423.                     }
  424.                     break;
  425.                 case 't':
  426.                 case 'T':
  427.                     addStr((char*)buf.c_str());
  428.                     buf = "";
  429.                     toTemp();
  430.                     break;
  431.                 case 'm':
  432.                 case 'M':
  433.                     addStr((char*)buf.c_str());
  434.                     buf = "";
  435.                     fromTemp();
  436.                     break;
  437.                 case 'd':
  438.                 case 'D':
  439.                     addStr((char*)buf.c_str());
  440.                     buf = "";
  441.                     return;
  442.                 case '+':
  443.                     addStr((char*)buf.c_str());
  444.                     buf = "";
  445.                     addition();
  446.                     break;
  447.                 case '-':
  448.                     addStr((char*)buf.c_str());
  449.                     buf = "";
  450.                     subtraction();
  451.                     break;
  452.                 case '!':
  453.                     addStr((char*)buf.c_str());
  454.                     buf = "";
  455.                     multiplication();
  456.                     break;
  457.                 case '$':
  458.                     addStr((char*)buf.c_str());
  459.                     buf = "";
  460.                     getQuotient();
  461.                     break;
  462.                 case '%':
  463.                     addStr((char*)buf.c_str());
  464.                     buf = "";
  465.                     getSurplus();
  466.                     break;
  467. #ifdef EXTENDED
  468.                 case '^':
  469.                     addStr((char*)buf.c_str());
  470.                     buf = "";
  471.                     getXor();
  472.                     break;
  473.                 case 'h':
  474.                 case 'H':
  475.                     addStr((char*)buf.c_str());
  476.                     buf = "";
  477.                     excHange();
  478.                     break;
  479. #endif
  480.                 default:
  481.                     buf += fName[--ps];
  482.             }
  483.         }else
  484.             buf += fName[ps];
  485.         ps++;
  486.     }
  487.     if(strlen((char*)buf.c_str())>0)addStr((char*)buf.c_str());
  488. }
  489. inline stack<int> Pxem::getStack() const{   return pStack;}
  490. inline void Pxem::print(){while(out());}
  491. inline bool Pxem::out(){
  492.     if(pStack.empty())return false;
  493.     int aaa=pStack.top();
  494.     putchar(aaa);
  495.     pStack.pop();
  496.     return true;
  497. }
  498. inline void Pxem::numOut(){
  499.     if(pStack.empty())return;
  500.     int aaa=pStack.top();
  501.     printf("%d",aaa);
  502.     pStack.pop();
  503. }
  504. inline void Pxem::input(){
  505.     int aaa=getchar();
  506.     pStack.push(aaa);
  507. }
  508. inline void Pxem::numInput(){
  509.     int aaa;
  510.     scanf("%d",&aaa);
  511.     pStack.push(aaa);
  512. }
  513. inline void Pxem::copy(){
  514.     int i=pStack.top();
  515.     pStack.push(i);
  516. }
  517. inline void Pxem::throwAway(){if(!pStack.empty())pStack.pop();}
  518. void Pxem::inverse(){
  519.     queue<int>fuga;
  520.     while(!pStack.empty()){
  521.         fuga.push((int)pStack.top());
  522.         pStack.pop();
  523.     }
  524.     while(!fuga.empty()){
  525.         pStack.push(fuga.front());
  526.         fuga.pop();
  527.     }
  528. }
  529. inline void Pxem::fileRead(){addStr(fCont);}
  530. void Pxem::emu(){
  531.     Pxem newPxem(fCont,fCont,pStack);
  532.     newPxem.run();
  533.     stack<int>aaa=newPxem.getStack();
  534.     stack<int>bbb;
  535.     while(!aaa.empty()){
  536.         bbb.push((int)aaa.top());
  537.         aaa.pop();
  538.     }
  539.     while(!bbb.empty()){
  540.         pStack.push(bbb.top());
  541.         bbb.pop();
  542.     }
  543. }
  544. inline void Pxem::getRand(){
  545.     int aaa=rand()%pStack.top();
  546.     pStack.pop();
  547.     pStack.push(aaa);
  548. }
  549. inline void Pxem::toTemp(){
  550.     if(pStack.empty())return;
  551.     temp=pStack.top();
  552.     pStack.pop();
  553.     used=true;
  554. }
  555. inline void Pxem::fromTemp(){
  556.     if(used)pStack.push(temp);
  557. }
  558. void Pxem::addition(){
  559.     if(pStack.size()<2)return;
  560.     int aa=pStack.top();
  561.     pStack.pop();
  562.     int bb=pStack.top();
  563.     pStack.pop();
  564.     pStack.push(aa+bb);
  565. }
  566. void Pxem::subtraction(){
  567.     if(pStack.size()<2)return;
  568.     int aa=pStack.top();
  569.     pStack.pop();
  570.     int bb=pStack.top();
  571.     pStack.pop();
  572.     pStack.push(abs(aa-bb));
  573. }
  574. void Pxem::multiplication(){
  575.     if(pStack.size()<2)return;
  576.     int aa=pStack.top();
  577.     pStack.pop();
  578.     int bb=pStack.top();
  579.     pStack.pop();
  580.     pStack.push(aa*bb);
  581. }
  582. void Pxem::getQuotient(){
  583.     if(pStack.size()<2)return;
  584.     int aa=pStack.top();
  585.     pStack.pop();
  586.     int bb=pStack.top();
  587.     pStack.pop();
  588.     pStack.push(aa>bb?aa/bb:bb/aa);
  589. }
  590. void Pxem::getSurplus(){
  591.     if(pStack.size()<2)return;
  592.     int aa=pStack.top();
  593.     pStack.pop();
  594.     int bb=pStack.top();
  595.     pStack.pop();
  596.     pStack.push(aa>bb?aa%bb:bb%aa);
  597. }
  598. void Pxem::getXor(){
  599.     if(pStack.size()<2)return;
  600.     int aa=pStack.top();
  601.     pStack.pop();
  602.     int bb=pStack.top();
  603.     pStack.pop();
  604.     pStack.push(aa^bb);
  605. }
  606. void Pxem::excHange(){
  607.     if(pStack.size()<2)return;
  608.     int aa=pStack.top();
  609.     pStack.pop();
  610.     int bb=pStack.top();
  611.     pStack.pop();
  612.     pStack.push(aa);
  613.     pStack.push(bb);
  614. }
  615. void Pxem::addStr(char* str){
  616.     int leng=strlen(str);
  617.     while(leng--)pStack.push((int)str[leng]);
  618. }
  619. int main(){
  620.     //puts(FILENAME),puts(CONTENT);
  621.     Pxem(FILENAME,CONTENT).run();
  622. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!