API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 21st, 2017
56
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.37 KB | None | 0 0
raw download clone embed print report
  1.    1.
  2.       #include <vector>
  3.    2.
  4.       #include <list>
  5.    3.
  6.       #include <map>
  7.    4.
  8.       #include <set>
  9.    5.
  10.       #include <deque>
  11.    6.
  12.       #include <queue>
  13.    7.
  14.       #include <stack>
  15.    8.
  16.       #include <bitset>
  17.    9.
  18.       #include <algorithm>
  19.   10.
  20.       #include <functional>
  21.   11.
  22.       #include <numeric>
  23.   12.
  24.       #include <utility>
  25.   13.
  26.       #include <sstream>
  27.   14.
  28.       #include <iostream>
  29.   15.
  30.       #include <iomanip>
  31.   16.
  32.       #include <cstdio>
  33.   17.
  34.       #include <cmath>
  35.   18.
  36.       #include <cstdlib>
  37.   19.
  38.       #include <cctype>
  39.   20.
  40.       #include <string>
  41.   21.
  42.       #include <cstring>
  43.   22.
  44.       #include <cstdio>
  45.   23.
  46.       #include <cmath>
  47.   24.
  48.       #include <cstdlib>
  49.   25.
  50.       #include <ctime>
  51.   26.
  52.        
  53.   27.
  54.       using namespace std;
  55.   28.
  56.        
  57.   29.
  58.       //BEGINTEMPLATE_BY_ACRUSH_TOPCODER
  59.   30.
  60.       #define SIZE(X) ((int)(X.size()))//NOTES:SIZE(
  61.   31.
  62.       #define LENGTH(X) ((int)(X.length()))//NOTES:LENGTH(
  63.   32.
  64.       #define MP(X,Y) make_pair(X,Y)//NOTES:MP(
  65.   33.
  66.       typedef long long int64;//NOTES:int64
  67.   34.
  68.       typedef unsigned long long uint64;//NOTES:uint64
  69.   35.
  70.       #define two(X) (1<<(X))//NOTES:two(
  71.   36.
  72.       #define twoL(X) (((int64)(1))<<(X))//NOTES:twoL(
  73.   37.
  74.       #define contain(S,X) (((S)&two(X))!=0)//NOTES:contain(
  75.   38.
  76.       #define containL(S,X) (((S)&twoL(X))!=0)//NOTES:containL(
  77.   39.
  78.       const double pi=acos(-1.0);//NOTES:pi
  79.   40.
  80.       const double eps=1e-11;//NOTES:eps
  81.   41.
  82.       template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}//NOTES:checkmin(
  83.   42.
  84.       template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}//NOTES:checkmax(
  85.   43.
  86.       template<class T> inline T sqr(T x){return x*x;}//NOTES:sqr
  87.   44.
  88.       typedef pair<int,int> ipair;//NOTES:ipair
  89.   45.
  90.       template<class T> inline T lowbit(T n){return (n^(n-1))&n;}//NOTES:lowbit(
  91.   46.
  92.       template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));}//NOTES:countbit(
  93.   47.
  94.       //Numberic Functions
  95.   48.
  96.       template<class T> inline T gcd(T a,T b)//NOTES:gcd(
  97.   49.
  98.       {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
  99.   50.
  100.       template<class T> inline T lcm(T a,T b)//NOTES:lcm(
  101.   51.
  102.       {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
  103.   52.
  104.       template<class T> inline T euclide(T a,T b,T &x,T &y)//NOTES:euclide(
  105.   53.
  106.       {if(a<0){T d=euclide(-a,b,x,y);x=-x;return d;}
  107.   54.
  108.       if(b<0){T d=euclide(a,-b,x,y);y=-y;return d;}
  109.   55.
  110.       if(b==0){x=1;y=0;return a;}else{T d=euclide(b,a%b,x,y);T t=x;x=y;y=t-(a/b)*y;return d;}}
  111.   56.
  112.       template<class T> inline vector<pair<T,int> > factorize(T n)//NOTES:factorize(
  113.   57.
  114.       {vector<pair<T,int> > R;for (T i=2;n>1;){if (n%i==0){int C=0;for (;n%i==0;C++,n/=i);R.push_back(make_pair(i,C));}
  115.   58.
  116.       i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;}
  117.   59.
  118.       template<class T> inline bool isPrimeNumber(T n)//NOTES:isPrimeNumber(
  119.   60.
  120.       {if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
  121.   61.
  122.       template<class T> inline T eularFunction(T n)//NOTES:eularFunction(
  123.   62.
  124.       {vector<pair<T,int> > R=factorize(n);T r=n;for (int i=0;i<R.size();i++)r=r/R[i].first*(R[i].first-1);return r;}
  125.   63.
  126.       //Matrix Operations
  127.   64.
  128.       const int MaxMatrixSize=40;//NOTES:MaxMatrixSize
  129.   65.
  130.       template<class T> inline void showMatrix(int n,T A[MaxMatrixSize][MaxMatrixSize])//NOTES:showMatrix(
  131.   66.
  132.       {for (int i=0;i<n;i++){for (int j=0;j<n;j++)cout<<A[i][j];cout<<endl;}}
  133.   67.
  134.       template<class T> inline T checkMod(T n,T m) {return (n%m+m)%m;}//NOTES:checkMod(
  135.   68.
  136.       template<class T> inline void identityMatrix(int n,T A[MaxMatrixSize][MaxMatrixSize])//NOTES:identityMatrix(
  137.   69.
  138.       {for (int i=0;i<n;i++) for (int j=0;j<n;j++) A[i][j]=(i==j)?1:0;}
  139.   70.
  140.       template<class T> inline void addMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:addMatrix(
  141.   71.
  142.       {for (int i=0;i<n;i++) for (int j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];}
  143.   72.
  144.       template<class T> inline void subMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:subMatrix(
  145.   73.
  146.       {for (int i=0;i<n;i++) for (int j=0;j<n;j++) C[i][j]=A[i][j]-B[i][j];}
  147.   74.
  148.       template<class T> inline void mulMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//NOTES:mulMatrix(
  149.   75.
  150.       { T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];
  151.   76.
  152.       for (int i=0;i<n;i++) for (int j=0;j<n;j++) A[i][j]=_A[i][j],B[i][j]=_B[i][j],C[i][j]=0;
  153.   77.
  154.       for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++) C[i][j]+=A[i][k]*B[k][j];}
  155.   78.
  156.       template<class T> inline void addModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:addModMatrix(
  157.   79.
  158.       {for (int i=0;i<n;i++) for (int j=0;j<n;j++) C[i][j]=checkMod(A[i][j]+B[i][j],m);}
  159.   80.
  160.       template<class T> inline void subModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:subModMatrix(
  161.   81.
  162.       {for (int i=0;i<n;i++) for (int j=0;j<n;j++) C[i][j]=checkMod(A[i][j]-B[i][j],m);}
  163.   82.
  164.       template<class T> inline T multiplyMod(T a,T b,T m) {return (T)((((int64)(a)*(int64)(b)%(int64)(m))+(int64)(m))%(int64)(m));}//NOTES:multiplyMod(
  165.   83.
  166.       template<class T> inline void mulModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//NOTES:mulModMatrix(
  167.   84.
  168.       { T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];
  169.   85.
  170.       for (int i=0;i<n;i++) for (int j=0;j<n;j++) A[i][j]=_A[i][j],B[i][j]=_B[i][j],C[i][j]=0;
  171.   86.
  172.       for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++) C[i][j]=(C[i][j]+multiplyMod(A[i][k],B[k][j],m))%m;}
  173.   87.
  174.       template<class T> inline T powerMod(T p,int e,T m)//NOTES:powerMod(
  175.   88.
  176.       {if(e==0)return 1%m;else if(e%2==0){T t=powerMod(p,e/2,m);return multiplyMod(t,t,m);}else return multiplyMod(powerMod(p,e-1,m),p,m);}
  177.   89.
  178.       //Point&Line
  179.   90.
  180.       double dist(double x1,double y1,double x2,double y2){return sqrt(sqr(x1-x2)+sqr(y1-y2));}//NOTES:dist(
  181.   91.
  182.       double distR(double x1,double y1,double x2,double y2){return sqr(x1-x2)+sqr(y1-y2);}//NOTES:distR(
  183.   92.
  184.       template<class T> T cross(T x0,T y0,T x1,T y1,T x2,T y2){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);}//NOTES:cross(
  185.   93.
  186.       int crossOper(double x0,double y0,double x1,double y1,double x2,double y2)//NOTES:crossOper(
  187.   94.
  188.       {double t=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);if (fabs(t)<=eps) return 0;return (t<0)?-1:1;}
  189.   95.
  190.       bool isIntersect(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)//NOTES:isIntersect(
  191.   96.
  192.       {return crossOper(x1,y1,x2,y2,x3,y3)*crossOper(x1,y1,x2,y2,x4,y4)<0 && crossOper(x3,y3,x4,y4,x1,y1)*crossOper(x3,y3,x4,y4,x2,y2)<0;}
  193.   97.
  194.       bool isMiddle(double s,double m,double t){return fabs(s-m)<=eps || fabs(t-m)<=eps || (s<m)!=(t<m);}//NOTES:isMiddle(
  195.   98.
  196.       //Translator
  197.   99.
  198.       bool isUpperCase(char c){return c>='A' && c<='Z';}//NOTES:isUpperCase(
  199.  100.
  200.       bool isLowerCase(char c){return c>='a' && c<='z';}//NOTES:isLowerCase(
  201.  101.
  202.       bool isLetter(char c){return c>='A' && c<='Z' || c>='a' && c<='z';}//NOTES:isLetter(
  203.  102.
  204.       bool isDigit(char c){return c>='0' && c<='9';}//NOTES:isDigit(
  205.  103.
  206.       char toLowerCase(char c){return (isUpperCase(c))?(c+32):c;}//NOTES:toLowerCase(
  207.  104.
  208.       char toUpperCase(char c){return (isLowerCase(c))?(c-32):c;}//NOTES:toUpperCase(
  209.  105.
  210.       template<class T> string toString(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}//NOTES:toString(
  211.  106.
  212.       int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}//NOTES:toInt(
  213.  107.
  214.       int64 toInt64(string s){int64 r=0;istringstream sin(s);sin>>r;return r;}//NOTES:toInt64(
  215.  108.
  216.       double toDouble(string s){double r=0;istringstream sin(s);sin>>r;return r;}//NOTES:toDouble(
  217.  109.
  218.       template<class T> void stoa(string s,int &n,T A[]){n=0;istringstream sin(s);for(T v;sin>>v;A[n++]=v);}//NOTES:stoa(
  219.  110.
  220.       template<class T> void atos(int n,T A[],string &s){ostringstream sout;for(int i=0;i<n;i++){if(i>0)sout<<' ';sout<<A[i];}s=sout.str();}//NOTES:atos(
  221.  111.
  222.       template<class T> void atov(int n,T A[],vector<T> &vi){vi.clear();for (int i=0;i<n;i++) vi.push_back(A[i]);}//NOTES:atov(
  223.  112.
  224.       template<class T> void vtoa(vector<T> vi,int &n,T A[]){n=vi.size();for (int i=0;i<n;i++)A[i]=vi[i];}//NOTES:vtoa(
  225.  113.
  226.       template<class T> void stov(string s,vector<T> &vi){vi.clear();istringstream sin(s);for(T v;sin>>v;vi.push_bakc(v));}//NOTES:stov(
  227.  114.
  228.       template<class T> void vtos(vector<T> vi,string &s){ostringstream sout;for (int i=0;i<vi.size();i++){if(i>0)sout<<' ';sout<<vi[i];}s=sout.str();}//NOTES:vtos(
  229.  115.
  230.       //Fraction
  231.  116.
  232.       template<class T> struct Fraction{T a,b;Fraction(T a=0,T b=1);string toString();};//NOTES:Fraction
  233.  117.
  234.       template<class T> Fraction<T>::Fraction(T a,T b){T d=gcd(a,b);a/=d;b/=d;if (b<0) a=-a,b=-b;this->a=a;this->b=b;}
  235.  118.
  236.       template<class T> string Fraction<T>::toString(){ostringstream sout;sout<<a<<"/"<<b;return sout.str();}
  237.  119.
  238.       template<class T> Fraction<T> operator+(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b+q.a*p.b,p.b*q.b);}
  239.  120.
  240.       template<class T> Fraction<T> operator-(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b-q.a*p.b,p.b*q.b);}
  241.  121.
  242.       template<class T> Fraction<T> operator*(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.a,p.b*q.b);}
  243.  122.
  244.       template<class T> Fraction<T> operator/(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b,p.b*q.a);}
  245.  123.
  246.       //ENDTEMPLATE_BY_ACRUSH_TOPCODER
  247.  124.
  248.        
  249.  125.
  250.       int main()
  251.  126.
  252.       {
  253.  127.
  254.       #ifdef _MSC_VER
  255.  128.
  256.       freopen("input.txt","r",stdin);
  257.  129.
  258.       #endif
  259.  130.
  260.       int v;
  261.  131.
  262.       while (scanf("%d",&v)!=-1 && v!=42)
  263.  132.
  264.       printf("%d\n",v);
  265.  133.
  266.       return 0;
  267.  134.
  268.       }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!