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

Added SRM/673-U/1A.cpp version [4dd570b916b5bddb]

            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 <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +static const unsigned MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + unsigned val;
           26  + mint():val(0){}
           27  + mint(int      x):val(x%MODVAL) {}
           28  + mint(unsigned x):val(x%MODVAL) {}
           29  + mint(LL       x):val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint operator+(mint x, mint y) { return x+=y; }
           35  +mint operator-(mint x, mint y) { return x-=y; }
           36  +mint operator*(mint x, mint y) { return x*=y; }
           37  +
           38  +class BearCavalry { public:
           39  + int countAssignments(vector <int> warriors, vector <int> horses)
           40  + {
           41  +  mint total = 0;
           42  +
           43  +  const int W = warriors[0];
           44  +  warriors.erase(warriors.begin());
           45  +  sort(warriors.begin(), warriors.end());
           46  +  sort(horses.begin(), horses.end());
           47  +
           48  +  for(int x=0; x<horses.size(); ++x) {
           49  +   const int H = horses[x];
           50  +   vector<int> hs(horses.begin(), horses.begin()+x);
           51  +   hs.insert(hs.end(), horses.begin()+x+1, horses.end());
           52  +   total += cnt(W*H, warriors, hs);
           53  +  }
           54  +  return total.val;
           55  + }
           56  +
           57  + mint cnt(int TOP, vector<int> w, vector<int> h)
           58  + {
           59  +  mint total = 1;
           60  +  for(int i=0; i<w.size(); ++i) {
           61  +   int W = w[w.size()-1-i];
           62  +
           63  +   int c=0;
           64  +   for(int hk: h)
           65  +    c += (hk*W < TOP);
           66  +   c -= i;
           67  +   if(c <= 0)
           68  +    return 0;
           69  +   total *= c;
           70  +  }
           71  +  return total;
           72  + }
           73  +};
           74  +
           75  +// BEGIN CUT HERE
           76  +#include <ctime>
           77  +double start_time; string timer()
           78  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           79  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           80  + { os << "{ ";
           81  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           82  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           83  +void verify_case(const int& Expected, const int& Received) {
           84  + bool ok = (Expected == Received);
           85  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           86  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           87  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           88  +#define END  verify_case(_, BearCavalry().countAssignments(warriors, horses));}
           89  +int main(){
           90  +
           91  +CASE(0)
           92  + int warriors_[] = {5,8,4,8};
           93  +   vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*warriors_));
           94  + int horses_[] = {19,40,25,20};
           95  +   vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_));
           96  + int _ = 2;
           97  +END
           98  +CASE(1)
           99  + int warriors_[] = {1,1};
          100  +   vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*warriors_));
          101  + int horses_[] = {1,1};
          102  +   vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_));
          103  + int _ = 0;
          104  +END
          105  +CASE(2)
          106  + int warriors_[] = {10,2,10};
          107  +   vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*warriors_));
          108  + int horses_[] = {100,150,200};
          109  +   vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_));
          110  + int _ = 3;
          111  +END
          112  +CASE(3)
          113  + int warriors_[] = {10,20};
          114  +   vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*warriors_));
          115  + int horses_[] = {1,3};
          116  +   vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_));
          117  + int _ = 1;
          118  +END
          119  +CASE(4)
          120  + int warriors_[] = {20,20,25,23,24,24,21};
          121  +   vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*warriors_));
          122  + int horses_[] = {20,25,25,20,25,23,20};
          123  +   vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_));
          124  + int _ = 0;
          125  +END
          126  +CASE(5)
          127  + int warriors_[] = {970,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,
          128  +800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800};
          129  +   vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*warriors_));
          130  + int horses_[] = {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,
          131  +1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,
          132  +1000,1000,1000,1000,1000,1000,1000,1000,1000,1000};
          133  +   vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_));
          134  + int _ = 318608048;
          135  +END
          136  +/*
          137  +CASE(6)
          138  + int warriors_[] = ;
          139  +   vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*warriors_));
          140  + int horses_[] = ;
          141  +   vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_));
          142  + int _ = ;
          143  +END
          144  +CASE(7)
          145  + int warriors_[] = ;
          146  +   vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*warriors_));
          147  + int horses_[] = ;
          148  +   vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_));
          149  + int _ = ;
          150  +END
          151  +*/
          152  +}
          153  +// END CUT HERE

Added SRM/673-U/1B-U.cpp version [b637a94f34ab84c4]

            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 <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +static unsigned MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + unsigned val;
           26  + mint():val(0){}
           27  + mint(int      x):val(x%MODVAL) {}
           28  + mint(unsigned x):val(x%MODVAL) {}
           29  + mint(LL       x):val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint operator+(mint x, mint y) { return x+=y; }
           35  +mint operator-(mint x, mint y) { return x-=y; }
           36  +mint operator*(mint x, mint y) { return x*=y; }
           37  +
           38  +vector< vector<mint> > CP_;
           39  +mint C(int n, int k) {
           40  + while( CP_.size() <= n ) {
           41  +  int nn = CP_.size();
           42  +  CP_.push_back(vector<mint>(nn+1,1));
           43  +  for(int kk=1; kk<nn; ++kk)
           44  +   CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
           45  + }
           46  + return k<0 || n<k ? 0 : CP_[n][k];
           47  +}
           48  +
           49  +class BearPermutations { public:
           50  + int countPermutations(int N, int S, int MOD)
           51  + {
           52  +  MODVAL = MOD;
           53  +  return pat_below(N, S).val;
           54  + }
           55  +
           56  + mint pat_below(int N, int S) {
           57  +  mint total = 0;
           58  +  for(int s=0; s<=S; ++s)
           59  +   total += pat_exact(N, s);
           60  +  return total;
           61  + }
           62  +
           63  + vector<int> memo3;
           64  + int pat_exact(int N, int S) {
           65  +  memo3.resize(101*101, -1);
           66  +  auto key = N*101+S;
           67  +  if(memo3[key]!=-1)
           68  +   return memo3[key];
           69  +
           70  +  mint total = 0;
           71  +  for(int c=0; c<N; ++c)
           72  +   total += pat_center_exact(N, c, S);
           73  +  return memo3[key] = total.val;
           74  + }
           75  +
           76  + vector<int> memo2;
           77  + int pat_exact_shifted(int N, int S, int score_offset) {
           78  +  memo2.resize(101*101*101, -1);
           79  +  auto key = (N*101+score_offset)*101+S;
           80  +  if(memo2[key]!=-1)
           81  +   return memo2[key];
           82  +
           83  +  mint total = 0;
           84  +  for(int c=0; c<N; ++c)
           85  +   if(score_offset+c <= S)
           86  +    total += pat_center_exact(N, c, S-(score_offset+c));
           87  +  return memo2[key]=total.val;
           88  + }
           89  +
           90  + vector<int> memo;
           91  + int pat_center_exact(int N, int c, int S)
           92  + {
           93  +  c = min(c, N-1-c);
           94  +
           95  +  if(N==1)
           96  +   return (S==0 ? 1 : 0);
           97  +  if(c==0 || c==N-1)
           98  +   return pat_exact(N-1, S);
           99  +
          100  +  memo.resize(101*101*101, -1);
          101  +  auto key = (N*101+c)*101+S;
          102  +  if(memo[key]!=-1)
          103  +   return memo[key];
          104  +
          105  +  LL total = 0;
          106  +  for(int cl=0; cl<c; ++cl)
          107  +  for(int SS=0; SS<=S; ++SS)
          108  +   total += ((LL)pat_center_exact(c, cl, SS) * pat_exact_shifted(N-c-1, S-SS, (c-cl)+1)) % MODVAL;
          109  +  return memo[key] = (total * C(N-1, c)).val;
          110  + }
          111  +};
          112  +
          113  +// BEGIN CUT HERE
          114  +#include <ctime>
          115  +double start_time; string timer()
          116  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          117  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          118  + { os << "{ ";
          119  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          120  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          121  +void verify_case(const int& Expected, const int& Received) {
          122  + bool ok = (Expected == Received);
          123  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          124  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          125  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          126  +#define END  verify_case(_, BearPermutations().countPermutations(N, S, MOD));}
          127  +int main(){
          128  +
          129  +CASE(0)
          130  + int N = 3;
          131  + int S = 1;
          132  + int MOD = 71876209;
          133  + int _ = 4;
          134  +END
          135  +CASE(1)
          136  + int N = 4;
          137  + int S = 0;
          138  + int MOD = 1000003;
          139  + int _ = 8;
          140  +END
          141  +CASE(2)
          142  + int N = 4;
          143  + int S = 1;
          144  + int MOD = 483128897;
          145  + int _ = 8;
          146  +END
          147  +CASE(3)
          148  + int N = 5;
          149  + int S = 3;
          150  + int MOD = 907283243;
          151  + int _ = 82;
          152  +END
          153  +CASE(4)
          154  + int N = 5;
          155  + int S = 100;
          156  + int MOD = 101;
          157  + int _ = 19;
          158  +END
          159  +CASE(5)
          160  + int N = 20;
          161  + int S = 30;
          162  + int MOD = 3;
          163  + int _ = 2;
          164  +END
          165  +CASE(6)
          166  + int N = 100;
          167  + int S = 100;
          168  + int MOD = 1000000007;
          169  + int _ = -1;
          170  +END
          171  +/*
          172  +CASE(7)
          173  + int N = ;
          174  + int S = ;
          175  + int MOD = ;
          176  + int _ = ;
          177  +END
          178  +*/
          179  +}
          180  +// END CUT HERE