• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/524-U/1A.cpp version [d971d0647e4bd58e]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class MagicDiamonds { public:
           29  + long long minimalTransfer(long long n)
           30  + {
           31  +  if( n <= 3 )
           32  +   return n;
           33  +  for(LL p=2; p*p<=n && p<n; ++p)
           34  +   if( n%p == 0 )
           35  +    return 1;
           36  +  return 2;
           37  + }
           38  +};
           39  +
           40  +// BEGIN CUT HERE
           41  +#include <ctime>
           42  +double start_time; string timer()
           43  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           44  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           45  + { os << "{ ";
           46  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           47  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           48  +void verify_case(const long long& Expected, const long long& Received) {
           49  + bool ok = (Expected == Received);
           50  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           51  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           52  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           53  +#define END  verify_case(_, MagicDiamonds().minimalTransfer(n));}
           54  +int main(){
           55  +
           56  +CASE(0)
           57  + long long n = 2LL;
           58  + long long _ = 2LL;
           59  +END
           60  +CASE(1)
           61  + long long n = 4294967297LL;
           62  + long long _ = 1LL;
           63  +END
           64  +CASE(2)
           65  + long long n = 2147483647LL;
           66  + long long _ = 2LL;
           67  +END
           68  +CASE(3)
           69  + long long n = 1LL;
           70  + long long _ = 1LL;
           71  +END
           72  +CASE(4)
           73  + long long n = 1000000000000LL;
           74  + long long _ = -1LL;
           75  +END
           76  +/*
           77  +CASE(5)
           78  + long long n = LL;
           79  + long long _ = LL;
           80  +END
           81  +*/
           82  +}
           83  +// END CUT HERE

Added SRM/524-U/1B.cpp version [38ff0d11552da11a]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class LongestSequence { public:
           29  + int maxLength(vector <int> C)
           30  + {
           31  +  vector<int> P, N;
           32  +  for(int i=0; i<C.size(); ++i)
           33  +   if( C[i]<0 )
           34  +    N.push_back(-C[i]);
           35  +   else
           36  +    P.push_back(+C[i]);
           37  +  sort(P.begin(), P.end());
           38  +  sort(N.begin(), N.end());
           39  +  if( P.empty() || N.empty() )
           40  +   return -1;
           41  +
           42  +  int L = 0, R = 10000000;
           43  +  while( R-L > 1 ) {
           44  +   int C = (L+R)/2;
           45  +   (has_loop(N, P, C) ? R : L) = C;
           46  +  }
           47  +  return L;
           48  + }
           49  +
           50  + bool has_loop(const vector<int>& N, const vector<int>& P, int MAX)
           51  + {
           52  +  vector<bool> vis(MAX+1, false);
           53  +  queue<int> Q;
           54  +  Q.push(0);
           55  +  vis[0] = true;
           56  +  while( !Q.empty() ) {
           57  +   int v = Q.front();
           58  +   Q.pop();
           59  +   for(int i=0; i<N.size(); ++i)
           60  +    if( v - N[i] == 0 )
           61  +     return true;
           62  +    else if( v-N[i] > 0 && !vis[v-N[i]] )
           63  +     {vis[v-N[i]]=true; Q.push(v-N[i]);}
           64  +   for(int i=0; i<P.size(); ++i)
           65  +    if( v+P[i] <= MAX && !vis[v+P[i]] )
           66  +     {vis[v+P[i]]=true; Q.push(v+P[i]);}
           67  +  }
           68  +  return false;
           69  + }
           70  +};
           71  +
           72  +// BEGIN CUT HERE
           73  +#include <ctime>
           74  +double start_time; string timer()
           75  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           76  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           77  + { os << "{ ";
           78  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           79  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           80  +void verify_case(const int& Expected, const int& Received) {
           81  + bool ok = (Expected == Received);
           82  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           83  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           84  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           85  +#define END  verify_case(_, LongestSequence().maxLength(C));}
           86  +int main(){
           87  +
           88  +CASE(0)
           89  + int C_[] = {-2,3};
           90  +   vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
           91  + int _ = 3;
           92  +END
           93  +CASE(1)
           94  + int C_[] = {524};
           95  +   vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
           96  + int _ = -1;
           97  +END
           98  +CASE(2)
           99  + int C_[] = {1, -1};
          100  +   vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
          101  + int _ = 0;
          102  +END
          103  +CASE(3)
          104  + int C_[] = {11,-7};
          105  +   vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
          106  + int _ = 16;
          107  +END
          108  +CASE(4)
          109  + int C_[] = {-227,690,590,-524};
          110  +   vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
          111  + int _ = 713;
          112  +END
          113  +CASE(5)
          114  + int C_[] = {273,752,-738,-34,863,-21,-532,-824,-170,-130,206,346,836,149,-374,-807,55,-859,640,-103,266,-716,963,-274,-654,-429,-512,595,-253,-32,790,-884,-974,975,-493,-979,-548,423,-242,-443,-132,-868,-374,-854,-15,476,-950,968,740,799};
          115  +   vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
          116  + int _ = -1;
          117  +END
          118  +CASE(6)
          119  + int C_[] = {3,4,3,3,1,4,4,-5,3,1,5,5,3,2,-1,-5,-4,2,-4,2,-2,-2,1,-5,4,-3,-3,4,2,-1,2,-4,1,4,-4,-2,4,-5,0,-4,5,3,-5,1,0,0,4,5,-5,-5};
          120  +   vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_));
          121  + int _ = -1;
          122  +END
          123  +
          124  +}
          125  +// END CUT-1000 HERE

Added SRM/524-U/1C-U.cpp version [f38a8ea9a6bc4e27]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +static const int MODVAL = 1000000009; // must be prime for op/
           29  +struct mint
           30  +{
           31  + int val;
           32  + mint():val(0){}
           33  + mint(int    x):val(x%MODVAL) {} // x>=0
           34  + mint(size_t x):val(x%MODVAL) {} // x>=0
           35  + mint(LL     x):val(x%MODVAL) {} // x>=0
           36  +};
           37  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           38  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           39  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           40  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           41  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
           42  +mint operator+(mint x, mint y) { return x+=y; }
           43  +mint operator-(mint x, mint y) { return x-=y; }
           44  +mint operator*(mint x, mint y) { return x*=y; }
           45  +mint operator/(mint x, mint y) { return x/=y; }
           46  +vector<mint> FAC_(1,1);
           47  +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
           48  +mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
           49  +
           50  +class AxonometricProjection { public:
           51  + int howManyWays(vector <int> left, vector <int> front)
           52  + {
           53  +  mint ans = 1;
           54  +  sort(left.begin(), left.end());
           55  +  sort(front.begin(), front.end());
           56  +  ans *= perm(left);
           57  +  ans *= perm(front);
           58  +  for(int i=0, k=0; i<left.size() || k<front.size(); )
           59  +  {
           60  +   if( k<front.size() && (i==left.size() || front[k]<left[i]) )
           61  +   {
           62  +    // advance k
           63  +    int h = front[k];
           64  +    int len = 0;
           65  +    while( k!=front.size() && front[k]==h )
           66  +     ++k, ++len;
           67  +    ans *= choose(h, len);
           68  +   }
           69  +   else if( i<left.size() && (k==front.size() || left[i]<front[k]) )
           70  +   {
           71  +    // advance i
           72  +    int h = left[i];
           73  +    int len = 0;
           74  +    while( i!=left.size() && left[i]==h )
           75  +     ++i, ++len;
           76  +    ans *= choose(h, len);
           77  +   }
           78  +   else
           79  +   {
           80  +    // both
           81  +    int h = left[i];
           82  +    assert( h == front[k] );
           83  +    int len1 = 0, len2 = 0;
           84  +    while( i!=left.size() && left[i]==h )
           85  +     ++i, ++len1;
           86  +    while( k!=front.size() && front[k]==h )
           87  +     ++k, ++len2;
           88  +    ans *= choose2(h, len1, len2);
           89  +   }
           90  +  }
           91  +  return ans.val;
           92  + }
           93  +
           94  + mint perm(const vector<int>& x)
           95  + {
           96  +  map<int,int> cat;
           97  +  for(int i=0; i<x.size(); ++i)
           98  +   cat[x[i]]++;
           99  +  mint r = FAC(x.size());
          100  +  for(map<int,int>::iterator it=cat.begin(); it!=cat.end(); ++it)
          101  +   r /= FAC(it->second);
          102  +  return r;
          103  + }
          104  +
          105  + mint choose(int h, int n)
          106  + {
          107  +  mint r = 0;
          108  +  for(int k=1; k<=n; ++k)
          109  +   r += C(n, k) * POW(h, n-k);
          110  +  return r;
          111  + }
          112  +
          113  + mint choose2(int h, int n1, int n2)
          114  + {
          115  +  return POW(2, n1+n2) + h * choose(h,n1) * choose(h,n2);
          116  + }
          117  +};
          118  +
          119  +// BEGIN CUT HERE
          120  +#include <ctime>
          121  +double start_time; string timer()
          122  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          123  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          124  + { os << "{ ";
          125  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          126  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          127  +void verify_case(const int& Expected, const int& Received) {
          128  + bool ok = (Expected == Received);
          129  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          130  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          131  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          132  +#define END  verify_case(_, AxonometricProjection().howManyWays(heightsOfLeftView, heightsOfFrontView));}
          133  +int main(){
          134  +
          135  +CASE(0)
          136  + int heightsOfLeftView_[] = {1,1};
          137  +   vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+sizeof(heightsOfLeftView_)/sizeof(*heightsOfLeftView_));
          138  + int heightsOfFrontView_[] = {1,1};
          139  +   vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontView_+sizeof(heightsOfFrontView_)/sizeof(*heightsOfFrontView_));
          140  + int _ = 7;
          141  +END
          142  +CASE(1)
          143  + int heightsOfLeftView_[] = {50,50,50,50,524};
          144  +   vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+sizeof(heightsOfLeftView_)/sizeof(*heightsOfLeftView_));
          145  + int heightsOfFrontView_[] = {524,524};
          146  +   vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontView_+sizeof(heightsOfFrontView_)/sizeof(*heightsOfFrontView_));
          147  + int _ = 104060401;
          148  +END
          149  +CASE(2)
          150  + int heightsOfLeftView_[] = {1,2,3,4,5,6,7,8,9,10};
          151  +   vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+sizeof(heightsOfLeftView_)/sizeof(*heightsOfLeftView_));
          152  + int heightsOfFrontView_[] = {1,2,3,4,5,6,7,8,9,10,11};
          153  +   vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontView_+sizeof(heightsOfFrontView_)/sizeof(*heightsOfFrontView_));
          154  + int _ = 0;
          155  +END
          156  +CASE(3)
          157  + int heightsOfLeftView_[] = {5,2,4,1};
          158  +   vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+sizeof(heightsOfLeftView_)/sizeof(*heightsOfLeftView_));
          159  + int heightsOfFrontView_[] = {5,2,4,0,1};
          160  +   vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontView_+sizeof(heightsOfFrontView_)/sizeof(*heightsOfFrontView_));
          161  + int _ = 429287;
          162  +END
          163  +CASE(4)
          164  + int heightsOfLeftView_[] = {5,2,4,52,24,524};
          165  +   vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+sizeof(heightsOfLeftView_)/sizeof(*heightsOfLeftView_));
          166  + int heightsOfFrontView_[] = {0,4,20,24,500,504,520,524};
          167  +   vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontView_+sizeof(heightsOfFrontView_)/sizeof(*heightsOfFrontView_));
          168  + int _ = 97065655;
          169  +END
          170  +/*
          171  +CASE(5)
          172  + int heightsOfLeftView_[] = ;
          173  +   vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+sizeof(heightsOfLeftView_)/sizeof(*heightsOfLeftView_));
          174  + int heightsOfFrontView_[] = ;
          175  +   vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontView_+sizeof(heightsOfFrontView_)/sizeof(*heightsOfFrontView_));
          176  + int _ = ;
          177  +END
          178  +CASE(6)
          179  + int heightsOfLeftView_[] = ;
          180  +   vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+sizeof(heightsOfLeftView_)/sizeof(*heightsOfLeftView_));
          181  + int heightsOfFrontView_[] = ;
          182  +   vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontView_+sizeof(heightsOfFrontView_)/sizeof(*heightsOfFrontView_));
          183  + int _ = ;
          184  +END
          185  +*/
          186  +}
          187  +// END CUT HERE