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

Added SRM/584-U/1A.cpp version [278a4ddd790b0339]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<double> CMP;
           21  +
           22  +class Egalitarianism { public:
           23  + int maxDifference(vector <string> isFriend, int d)
           24  + {
           25  +  int N = isFriend.size();
           26  +  int INF = 0x3fffffff;
           27  +  vector< vector<int> > g(N, vector<int>(N, INF));
           28  +  for(int x=0; x<N; ++x)
           29  +  for(int y=0; y<N; ++y)
           30  +   if(x==y)
           31  +    g[x][y] = 0;
           32  +   else if(isFriend[x][y]=='Y')
           33  +    g[x][y] = 1;
           34  +
           35  +  for(int k=0; k<N; ++k)
           36  +  for(int i=0; i<N; ++i)
           37  +  for(int j=0; j<N; ++j)
           38  +   g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
           39  +
           40  +  int maxd = 0;
           41  +  for(int x=0; x<N; ++x)
           42  +  for(int y=0; y<N; ++y)
           43  +   maxd = max(maxd, g[x][y]);
           44  +  return maxd==INF ? -1  : maxd*d;
           45  + }
           46  +};
           47  +
           48  +// BEGIN CUT HERE
           49  +#include <ctime>
           50  +double start_time; string timer()
           51  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           52  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           53  + { os << "{ ";
           54  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           55  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           56  +void verify_case(const int& Expected, const int& Received) {
           57  + bool ok = (Expected == Received);
           58  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           59  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           60  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           61  +#define END  verify_case(_, Egalitarianism().maxDifference(isFriend, d));}
           62  +int main(){
           63  +
           64  +CASE(0)
           65  + string isFriend_[] = {"NYN",
           66  + "YNY",
           67  + "NYN"};
           68  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
           69  + int d = 10;
           70  + int _ = 20;
           71  +END
           72  +CASE(1)
           73  + string isFriend_[] = {"NN",
           74  + "NN"};
           75  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
           76  + int d = 1;
           77  + int _ = -1;
           78  +END
           79  +CASE(2)
           80  + string isFriend_[] = {"NNYNNN",
           81  + "NNYNNN",
           82  + "YYNYNN",
           83  + "NNYNYY",
           84  + "NNNYNN",
           85  + "NNNYNN"};
           86  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
           87  + int d = 1000;
           88  + int _ = 3000;
           89  +END
           90  +CASE(3)
           91  + string isFriend_[] = {"NNYN",
           92  + "NNNY",
           93  + "YNNN",
           94  + "NYNN"};
           95  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
           96  + int d = 584;
           97  + int _ = -1;
           98  +END
           99  +CASE(4)
          100  + string isFriend_[] = {"NYNYYYN",
          101  + "YNNYYYN",
          102  + "NNNNYNN",
          103  + "YYNNYYN",
          104  + "YYYYNNN",
          105  + "YYNYNNY",
          106  + "NNNNNYN"};
          107  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
          108  + int d = 5;
          109  + int _ = 20;
          110  +END
          111  +CASE(5)
          112  + string isFriend_[] = {"NYYNNNNYYYYNNNN",
          113  + "YNNNYNNNNNNYYNN",
          114  + "YNNYNYNNNNYNNNN",
          115  + "NNYNNYNNNNNNNNN",
          116  + "NYNNNNYNNYNNNNN",
          117  + "NNYYNNYNNYNNNYN",
          118  + "NNNNYYNNYNNNNNN",
          119  + "YNNNNNNNNNYNNNN",
          120  + "YNNNNNYNNNNNYNN",
          121  + "YNNNYYNNNNNNNNY",
          122  + "YNYNNNNYNNNNNNN",
          123  + "NYNNNNNNNNNNNNY",
          124  + "NYNNNNNNYNNNNYN",
          125  + "NNNNNYNNNNNNYNN",
          126  + "NNNNNNNNNYNYNNN"}
          127  +;
          128  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
          129  + int d = 747;
          130  + int _ = 2988;
          131  +END
          132  +/*
          133  +CASE(6)
          134  + string isFriend_[] = {"NY",
          135  + "YN"};
          136  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
          137  + int d = 0;
          138  + int _ = 0;
          139  +END
          140  +CASE(7)
          141  + string isFriend_[] = ;
          142  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
          143  + int d = ;
          144  + int _ = ;
          145  +END
          146  +CASE(8)
          147  + string isFriend_[] = ;
          148  +   vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
          149  + int d = ;
          150  + int _ = ;
          151  +END
          152  +*/
          153  +}
          154  +// END CUT HERE

Added SRM/584-U/1B-U.cpp version [7cd5022ef19f47d8]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<double> CMP;
           21  +
           22  +template<typename T>
           23  +vector<int> compress(const vector<T>& xs, int origin = 0)
           24  +{
           25  + vector< pair<T,int> > xi;
           26  + for(int i=0; i<xs.size(); ++i)
           27  +  xi.push_back( make_pair(xs[i], i) );
           28  + sort(xi.begin(), xi.end());
           29  +
           30  + vector<int> result(xs.size());
           31  + for(int k=0,id=origin; k<xi.size(); ++k) {
           32  +  if(0<=k-1 && xi[k-1].first<xi[k].first)
           33  +   ++id;
           34  +  result[xi[k].second] = id;
           35  + }
           36  + return result;
           37  +}
           38  +
           39  +std::vector<int> compress(const std::vector<int>& xs)  // convert to 1-origin rank
           40  +{
           41  + set<int> s(xs.begin(), xs.end());
           42  + map<int,int> mp;
           43  + int ID = 1;
           44  + for(set<int>::iterator it=s.begin(); it!=s.end(); ++it)
           45  +  mp[*it] = ID++;
           46  +
           47  + std::vector<int> result(xs.size());
           48  + for(int k=0; k<xs.size(); ++k)
           49  +  result[k] = mp[xs[k]];
           50  + return result;
           51  +}
           52  +
           53  +LL C(LL n, LL k)
           54  +{
           55  + if(n<k)
           56  +  return 0;
           57  +
           58  + k = min(k, n-k);
           59  +
           60  + LL c = 1;
           61  + for(LL i=0; i<k; ++i)
           62  +  c *= n-i, c /= i+1;
           63  + return c;
           64  +}
           65  +
           66  +class Excavations { public:
           67  + long long count(vector <int> kind, vector <int> depth, vector <int> found, int K)
           68  + {
           69  +  depth = compress(depth, 1);
           70  +  int MD = *max_element(depth.begin(), depth.end());
           71  +
           72  +  map< int, vector<int> > kind_to_depth;
           73  +  set<int> found_set(found.begin(), found.end());
           74  +
           75  +  for(int i=0; i<kind.size(); ++i)
           76  +   kind_to_depth[kind[i]].push_back(depth[i]);
           77  +
           78  +  vector< vector<LL> > tbl_f(K+1, vector<LL>(MD+1));
           79  +  vector< vector<LL> > tbl_nf(K+1, vector<LL>(MD+1));
           80  +  for(int d=0; d<=MD; ++d)
           81  +   tbl_f[0][d] = tbl_nf[0][d] = 1;
           82  +
           83  +  for(map<int,vector<int> >::iterator it=kind_to_depth.begin(); it != kind_to_depth.end(); ++it) {
           84  +   bool f = !!found_set.count(it->first);
           85  +   vector<int> ds = it->second;
           86  +   sort(ds.begin(), ds.end());
           87  +   vector< vector<LL> > tbl2 = calc_table(K, MD, ds, f);
           88  +   vector< vector<LL> >& tbl = (f ? tbl_f : tbl_nf);
           89  +   tbl = combine(K, MD, tbl, tbl2);
           90  +  }
           91  +
           92  +  LL total = 0;
           93  +  for(int k=0; k<=K; ++k)
           94  +   total += cross(tbl_f[k], tbl_nf[K-k]);
           95  +  return total;
           96  + }
           97  +
           98  + LL cross(const vector<LL>& f, const vector<LL>& n)
           99  + {
          100  +  vector< pair<int,LL> > pf;
          101  +  for(int d=0; d<f.size(); ++d) {
          102  +   LL cnt = (d==0 ? f[d] : f[d]-f[d-1]);
          103  +   if(cnt) {
          104  +    pf.push_back(make_pair(d, cnt));
          105  +   }
          106  +  }
          107  +
          108  +  vector< pair<int,LL> > nf;
          109  +  for(int d=0; d<n.size(); ++d) {
          110  +   LL cnt = (d==n.size()-1 ? n[d] : n[d]-n[d+1]);
          111  +   if(cnt) {
          112  +    nf.push_back(make_pair(d, cnt));
          113  +   }
          114  +  }
          115  +
          116  +  LL total = 0;
          117  +  for(int i=0; i<pf.size(); ++i)
          118  +  for(int k=0; k<nf.size(); ++k)
          119  +  {
          120  +   if(pf[i].first <= nf[k].first)
          121  +    total += pf[i].second * nf[k].second;
          122  +  }
          123  +  return total;
          124  + }
          125  +
          126  + vector< vector<LL> > calc_table(int K, int D, const vector<int>& ds, bool found)
          127  + {
          128  +  vector< vector<LL> > tbl(K+1, vector<LL>(D+1));
          129  +  for(int d=0; d<=D; ++d)
          130  +  {
          131  +   int num_discover = upper_bound(ds.begin(), ds.end(), d) - ds.begin();
          132  +   for(int k=0; k<=K; ++k)
          133  +    tbl[k][d] = (found ? (k==0 ? 0 : C(num_discover, k)) : C(ds.size()-num_discover, k));
          134  +  }
          135  +  return tbl;
          136  + }
          137  +
          138  + vector< vector<LL> > combine(int K, int D, const vector<vector<LL> >& s, const vector<vector<LL> >& t)
          139  + {
          140  +  vector< vector<LL> > r(K+1, vector<LL>(D+1));
          141  +  for(int ks=0; ks<=K; ++ks)
          142  +  for(int kt=0; kt<=K; ++kt) if(ks+kt<=K)
          143  +   for(int d=0; d<=D; ++d)
          144  +    r[ks+kt][d] += s[ks][d] * t[kt][d];
          145  +  return r;
          146  + }
          147  +};
          148  +
          149  +// BEGIN CUT HERE
          150  +#include <ctime>
          151  +double start_time; string timer()
          152  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          153  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          154  + { os << "{ ";
          155  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          156  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          157  +void verify_case(const long long& Expected, const long long& Received) {
          158  + bool ok = (Expected == Received);
          159  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          160  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          161  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          162  +#define END  verify_case(_, Excavations().count(kind, depth, found, K));}
          163  +int main(){
          164  +
          165  +CASE(0)
          166  + int kind_[] = {1, 1, 2, 2};
          167  +   vector <int> kind(kind_, kind_+sizeof(kind_)/sizeof(*kind_));
          168  + int depth_[] = {10, 15, 10, 20};
          169  +   vector <int> depth(depth_, depth_+sizeof(depth_)/sizeof(*depth_));
          170  + int found_[] = {1};
          171  +   vector <int> found(found_, found_+sizeof(found_)/sizeof(*found_));
          172  + int K = 2;
          173  + long long _ = 3LL;
          174  +END
          175  +CASE(1)
          176  + int kind_[] = {1, 1, 2, 2};
          177  +   vector <int> kind(kind_, kind_+sizeof(kind_)/sizeof(*kind_));
          178  + int depth_[] = {10, 15, 10, 20};
          179  +   vector <int> depth(depth_, depth_+sizeof(depth_)/sizeof(*depth_));
          180  + int found_[] = {1, 2};
          181  +   vector <int> found(found_, found_+sizeof(found_)/sizeof(*found_));
          182  + int K = 2;
          183  + long long _ = 4LL;
          184  +END
          185  +CASE(2)
          186  + int kind_[] = {1, 2, 3, 4};
          187  +   vector <int> kind(kind_, kind_+sizeof(kind_)/sizeof(*kind_));
          188  + int depth_[] = {10, 10, 10, 10};
          189  +   vector <int> depth(depth_, depth_+sizeof(depth_)/sizeof(*depth_));
          190  + int found_[] = {1, 2};
          191  +   vector <int> found(found_, found_+sizeof(found_)/sizeof(*found_));
          192  + int K = 3;
          193  + long long _ = 0LL;
          194  +END
          195  +CASE(3)
          196  + int kind_[] = {1, 2, 2, 3, 1, 3, 2, 1, 2};
          197  +   vector <int> kind(kind_, kind_+sizeof(kind_)/sizeof(*kind_));
          198  + int depth_[] = {12512, 12859, 125, 1000, 99, 114, 125, 125, 114};
          199  +   vector <int> depth(depth_, depth_+sizeof(depth_)/sizeof(*depth_));
          200  + int found_[] = {1, 2, 3};
          201  +   vector <int> found(found_, found_+sizeof(found_)/sizeof(*found_));
          202  + int K = 7;
          203  + long long _ = 35LL;
          204  +END
          205  +CASE(4)
          206  + int kind_[] = {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50};
          207  +   vector <int> kind(kind_, kind_+sizeof(kind_)/sizeof(*kind_));
          208  + int depth_[] = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3};
          209  +   vector <int> depth(depth_, depth_+sizeof(depth_)/sizeof(*depth_));
          210  + int found_[] = {50};
          211  +   vector <int> found(found_, found_+sizeof(found_)/sizeof(*found_));
          212  + int K = 18;
          213  + long long _ = 9075135300LL;
          214  +END
          215  +/*
          216  +CASE(5)
          217  + int kind_[] = ;
          218  +   vector <int> kind(kind_, kind_+sizeof(kind_)/sizeof(*kind_));
          219  + int depth_[] = ;
          220  +   vector <int> depth(depth_, depth_+sizeof(depth_)/sizeof(*depth_));
          221  + int found_[] = ;
          222  +   vector <int> found(found_, found_+sizeof(found_)/sizeof(*found_));
          223  + int K = ;
          224  + long long _ = LL;
          225  +END
          226  +CASE(6)
          227  + int kind_[] = ;
          228  +   vector <int> kind(kind_, kind_+sizeof(kind_)/sizeof(*kind_));
          229  + int depth_[] = ;
          230  +   vector <int> depth(depth_, depth_+sizeof(depth_)/sizeof(*depth_));
          231  + int found_[] = ;
          232  +   vector <int> found(found_, found_+sizeof(found_)/sizeof(*found_));
          233  + int K = ;
          234  + long long _ = LL;
          235  +END
          236  + */
          237  +}
          238  +// END CUT HERE