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

Added SRM/TCO17-2B-U/1A.cpp version [5977a8407d058772]

            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  +class DengklekGaneshAndChains { public:
           23  + string getBestChains(vector<string> chains, vector<int> lengths)
           24  + {
           25  +  for (string& chain : chains)
           26  +   chain = make_it_lex_last(chain);
           27  +  sort(chains.begin(), chains.end());
           28  +
           29  +  string ans;
           30  +  for (int len : lengths)
           31  +  {
           32  +   string s = chains.back().substr(0, len);
           33  +   for (size_t i = 0; i < chains.size(); ++i)
           34  +    if(chains[i].substr(0, len) == s) {
           35  +     ans += s;
           36  +     chains.erase(chains.begin() + i);
           37  +     break;
           38  +    }
           39  +  }
           40  +  return ans;
           41  + }
           42  +
           43  + string make_it_lex_last(const string& s)
           44  + {
           45  +  string t = s;
           46  +  for (size_t i = 1; i < s.size(); ++i)
           47  +   t = max(t, s.substr(i) + s.substr(0, i));
           48  +  return t;
           49  + }
           50  +};
           51  +
           52  +// BEGIN CUT HERE
           53  +#include <ctime>
           54  +double start_time; string timer()
           55  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           56  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           57  + { os << "{ ";
           58  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           59  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           60  +void verify_case(const string& Expected, const string& Received) {
           61  + bool ok = (Expected == Received);
           62  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           63  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           64  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           65  +#define END  verify_case(_, DengklekGaneshAndChains().getBestChains(chains, lengths));}
           66  +int main(){
           67  +
           68  +CASE(0)
           69  + string chains_[] = {"topc", "oder", "open", "twob"};
           70  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
           71  + int lengths_[] = {2, 1, 3};
           72  +   vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_));
           73  + string _ = "wotrod";
           74  +END
           75  +CASE(1)
           76  + string chains_[] = {"ssh", "she", "see", "sea"};
           77  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
           78  + int lengths_[] = {2, 3, 2, 3};
           79  +   vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_));
           80  + string _ = "ssshesesee";
           81  +END
           82  +CASE(2)
           83  + string chains_[] = {"wri", "ter", "who", "are", "you"};
           84  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
           85  + int lengths_[] = {3};
           86  +   vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_));
           87  + string _ = "you";
           88  +END
           89  +CASE(3)
           90  + string chains_[] = {"harus", "imfyo"};
           91  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
           92  + int lengths_[] = {5, 5};
           93  +   vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_));
           94  + string _ = "yoimfushar";
           95  +END
           96  +/*
           97  +CASE(4)
           98  + string chains_[] = ;
           99  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          100  + int lengths_[] = ;
          101  +   vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_));
          102  + string _ = ;
          103  +END
          104  +CASE(5)
          105  + string chains_[] = ;
          106  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          107  + int lengths_[] = ;
          108  +   vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_));
          109  + string _ = ;
          110  +END
          111  +*/
          112  +}
          113  +// END CUT HERE

Added SRM/TCO17-2B-U/1B.cpp version [cfe4f511e056164f]

            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  +struct UnionFind
           23  +{
           24  + vector<int> uf, sz;
           25  + int nc;
           26  +
           27  + UnionFind(int N) : uf(N), sz(N, 1), nc(N)
           28  + {
           29  +  for (int i = 0; i<N; ++i) uf[i] = i;
           30  + }
           31  + int size()
           32  + {
           33  +  return nc;
           34  + }
           35  + int size(int a)
           36  + {
           37  +  return sz[Find(a)];
           38  + }
           39  + int Find(int a)
           40  + {
           41  +  return uf[a] == a ? a : uf[a] = Find(uf[a]);
           42  + }
           43  + // Semi-compression w.o. recursion.
           44  + //{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return a; }
           45  + bool Union(int a, int b)
           46  + {
           47  +  a = Find(a);
           48  +  b = Find(b);
           49  +  if (a != b)
           50  +  {
           51  +   if (sz[a] >= sz[b]) swap(a, b);
           52  +   uf[a] = b;
           53  +   sz[b] += sz[a];
           54  +   --nc;
           55  +  }
           56  +  return (a != b);
           57  + }
           58  +};
           59  +
           60  +static const unsigned MODVAL = 1000000007;
           61  +
           62  +class DengklekGaneshAndTree { public:
           63  + int getCount(string labels, vector <int> parents)
           64  + {
           65  +  const int N = labels.size();
           66  +
           67  +  vector<vector<int>> children(N);
           68  +  UnionFind uf(N);
           69  +  for (int i = 1; i < N; ++i) {
           70  +   int u = parents[i-1], v = i;
           71  +   children[u].push_back(v);
           72  +   if (labels[u] == labels[v])
           73  +    uf.Union(u, v);
           74  +  }
           75  +
           76  +  vector<int> level(N);
           77  +  {
           78  +   function<void(int, int)> rec; rec = [&](int v, int lv) {
           79  +    level[v] = lv;
           80  +    for (int u : children[v])
           81  +     rec(u, lv + 1);
           82  +   };
           83  +   rec(0, 0);
           84  +  }
           85  +
           86  +  map<int, int> lb, ub;
           87  +  for (int v = 0; v < N; ++v) {
           88  +   int r = uf.Find(v), lv = level[v];
           89  +   if (lb.count(r) == 0) {
           90  +    lb[r] = lv;
           91  +    ub[r] = lv;
           92  +   }
           93  +   else {
           94  +    lb[r] = min(lb[r], lv);
           95  +    ub[r] = max(ub[r], lv);
           96  +   }
           97  +  }
           98  +
           99  +  vector<pair<int, int>> rng;
          100  +  for(auto kv : lb)
          101  +   rng.emplace_back(kv.second, ub[kv.first]);
          102  +  int L = *max_element(level.begin(), level.end());
          103  +  return solve(rng, L);
          104  + }
          105  +
          106  + // Number of ways to cover [0,L] by choosing subset of |rng|s.
          107  + int solve(vector<pair<int, int>> rng, int L) {
          108  +  sort(rng.begin(), rng.end());
          109  +
          110  +  function<int(int, int)> rec;
          111  +  vector<int> memo(rng.size() * (L+2), -1);
          112  +  rec = [&](int i, int coveredUpto) {
          113  +   if (i == rng.size())
          114  +    return coveredUpto == L ? 1 : 0;
          115  +
          116  +   const int key = i*(L + 1) + (coveredUpto+1);
          117  +   if (memo[key] != -1)
          118  +    return memo[key];
          119  +
          120  +   if (coveredUpto + 2 <= rng[i].first)
          121  +    return memo[key] = 0;
          122  +   return memo[key] = (rec(i + 1, coveredUpto) + rec(i + 1, max(coveredUpto, rng[i].second))) % MODVAL;
          123  +  };
          124  +  return rec(0, -1);
          125  + }
          126  +};
          127  +
          128  +// BEGIN CUT HERE
          129  +#include <ctime>
          130  +double start_time; string timer()
          131  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          132  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          133  + { os << "{ ";
          134  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          135  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          136  +void verify_case(const int& Expected, const int& Received) {
          137  + bool ok = (Expected == Received);
          138  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          139  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          140  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          141  +#define END  verify_case(_, DengklekGaneshAndTree().getCount(labels, parents));}
          142  +int main(){
          143  +
          144  +CASE(0)
          145  + string labels = "seems";
          146  + int parents_[] = {0, 1, 0, 3};
          147  +   vector <int> parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_));
          148  + int _ = 5;
          149  +END
          150  +CASE(1)
          151  + string labels = "like";
          152  + int parents_[] = {0, 0, 0};
          153  +   vector <int> parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_));
          154  + int _ = 7;
          155  +END
          156  +CASE(2)
          157  + string labels = "a";
          158  + vector <int> parents;
          159  + int _ = 1;
          160  +END
          161  +CASE(3)
          162  + string labels = "coincidence";
          163  + int parents_[] = {0, 1, 2, 0, 2, 1, 4, 7, 7, 6};
          164  +   vector <int> parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_));
          165  + int _ = 218;
          166  +END
          167  +CASE(4)
          168  + string labels = "topcoderopenroundtwobgoodluckhavefun";
          169  + int parents_[] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
          170  +   vector <int> parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_));
          171  + int _ = 147418098;
          172  +END
          173  +/*
          174  +CASE(5)
          175  + string labels = ;
          176  + int parents_[] = ;
          177  +   vector <int> parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_));
          178  + int _ = ;
          179  +END
          180  +CASE(6)
          181  + string labels = ;
          182  + int parents_[] = ;
          183  +   vector <int> parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_));
          184  + int _ = ;
          185  +END
          186  +*/
          187  +}
          188  +// END CUT HERE