d335067c64 2017-07-08 kinaba: #include <iostream> d335067c64 2017-07-08 kinaba: #include <sstream> d335067c64 2017-07-08 kinaba: #include <iomanip> d335067c64 2017-07-08 kinaba: #include <vector> d335067c64 2017-07-08 kinaba: #include <string> d335067c64 2017-07-08 kinaba: #include <map> d335067c64 2017-07-08 kinaba: #include <set> d335067c64 2017-07-08 kinaba: #include <algorithm> d335067c64 2017-07-08 kinaba: #include <numeric> d335067c64 2017-07-08 kinaba: #include <iterator> d335067c64 2017-07-08 kinaba: #include <functional> d335067c64 2017-07-08 kinaba: #include <complex> d335067c64 2017-07-08 kinaba: #include <queue> d335067c64 2017-07-08 kinaba: #include <stack> d335067c64 2017-07-08 kinaba: #include <cmath> d335067c64 2017-07-08 kinaba: #include <cassert> d335067c64 2017-07-08 kinaba: #include <tuple> d335067c64 2017-07-08 kinaba: using namespace std; d335067c64 2017-07-08 kinaba: typedef long long LL; d335067c64 2017-07-08 kinaba: typedef complex<double> CMP; d335067c64 2017-07-08 kinaba: d335067c64 2017-07-08 kinaba: class DengklekGaneshAndChains { public: d335067c64 2017-07-08 kinaba: string getBestChains(vector<string> chains, vector<int> lengths) d335067c64 2017-07-08 kinaba: { d335067c64 2017-07-08 kinaba: for (string& chain : chains) d335067c64 2017-07-08 kinaba: chain = make_it_lex_last(chain); d335067c64 2017-07-08 kinaba: sort(chains.begin(), chains.end()); d335067c64 2017-07-08 kinaba: d335067c64 2017-07-08 kinaba: string ans; d335067c64 2017-07-08 kinaba: for (int len : lengths) d335067c64 2017-07-08 kinaba: { d335067c64 2017-07-08 kinaba: string s = chains.back().substr(0, len); d335067c64 2017-07-08 kinaba: for (size_t i = 0; i < chains.size(); ++i) d335067c64 2017-07-08 kinaba: if(chains[i].substr(0, len) == s) { d335067c64 2017-07-08 kinaba: ans += s; d335067c64 2017-07-08 kinaba: chains.erase(chains.begin() + i); d335067c64 2017-07-08 kinaba: break; d335067c64 2017-07-08 kinaba: } d335067c64 2017-07-08 kinaba: } d335067c64 2017-07-08 kinaba: return ans; d335067c64 2017-07-08 kinaba: } d335067c64 2017-07-08 kinaba: d335067c64 2017-07-08 kinaba: string make_it_lex_last(const string& s) d335067c64 2017-07-08 kinaba: { d335067c64 2017-07-08 kinaba: string t = s; d335067c64 2017-07-08 kinaba: for (size_t i = 1; i < s.size(); ++i) d335067c64 2017-07-08 kinaba: t = max(t, s.substr(i) + s.substr(0, i)); d335067c64 2017-07-08 kinaba: return t; d335067c64 2017-07-08 kinaba: } d335067c64 2017-07-08 kinaba: }; d335067c64 2017-07-08 kinaba: d335067c64 2017-07-08 kinaba: // BEGIN CUT HERE d335067c64 2017-07-08 kinaba: #include <ctime> d335067c64 2017-07-08 kinaba: double start_time; string timer() d335067c64 2017-07-08 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d335067c64 2017-07-08 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d335067c64 2017-07-08 kinaba: { os << "{ "; d335067c64 2017-07-08 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d335067c64 2017-07-08 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d335067c64 2017-07-08 kinaba: void verify_case(const string& Expected, const string& Received) { d335067c64 2017-07-08 kinaba: bool ok = (Expected == Received); d335067c64 2017-07-08 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d335067c64 2017-07-08 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } d335067c64 2017-07-08 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d335067c64 2017-07-08 kinaba: #define END verify_case(_, DengklekGaneshAndChains().getBestChains(chains, lengths));} d335067c64 2017-07-08 kinaba: int main(){ d335067c64 2017-07-08 kinaba: d335067c64 2017-07-08 kinaba: CASE(0) d335067c64 2017-07-08 kinaba: string chains_[] = {"topc", "oder", "open", "twob"}; d335067c64 2017-07-08 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); d335067c64 2017-07-08 kinaba: int lengths_[] = {2, 1, 3}; d335067c64 2017-07-08 kinaba: vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); d335067c64 2017-07-08 kinaba: string _ = "wotrod"; d335067c64 2017-07-08 kinaba: END d335067c64 2017-07-08 kinaba: CASE(1) d335067c64 2017-07-08 kinaba: string chains_[] = {"ssh", "she", "see", "sea"}; d335067c64 2017-07-08 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); d335067c64 2017-07-08 kinaba: int lengths_[] = {2, 3, 2, 3}; d335067c64 2017-07-08 kinaba: vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); d335067c64 2017-07-08 kinaba: string _ = "ssshesesee"; d335067c64 2017-07-08 kinaba: END d335067c64 2017-07-08 kinaba: CASE(2) d335067c64 2017-07-08 kinaba: string chains_[] = {"wri", "ter", "who", "are", "you"}; d335067c64 2017-07-08 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); d335067c64 2017-07-08 kinaba: int lengths_[] = {3}; d335067c64 2017-07-08 kinaba: vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); d335067c64 2017-07-08 kinaba: string _ = "you"; d335067c64 2017-07-08 kinaba: END d335067c64 2017-07-08 kinaba: CASE(3) d335067c64 2017-07-08 kinaba: string chains_[] = {"harus", "imfyo"}; d335067c64 2017-07-08 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); d335067c64 2017-07-08 kinaba: int lengths_[] = {5, 5}; d335067c64 2017-07-08 kinaba: vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); d335067c64 2017-07-08 kinaba: string _ = "yoimfushar"; d335067c64 2017-07-08 kinaba: END d335067c64 2017-07-08 kinaba: /* d335067c64 2017-07-08 kinaba: CASE(4) d335067c64 2017-07-08 kinaba: string chains_[] = ; d335067c64 2017-07-08 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); d335067c64 2017-07-08 kinaba: int lengths_[] = ; d335067c64 2017-07-08 kinaba: vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); d335067c64 2017-07-08 kinaba: string _ = ; d335067c64 2017-07-08 kinaba: END d335067c64 2017-07-08 kinaba: CASE(5) d335067c64 2017-07-08 kinaba: string chains_[] = ; d335067c64 2017-07-08 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); d335067c64 2017-07-08 kinaba: int lengths_[] = ; d335067c64 2017-07-08 kinaba: vector <int> lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); d335067c64 2017-07-08 kinaba: string _ = ; d335067c64 2017-07-08 kinaba: END d335067c64 2017-07-08 kinaba: */ d335067c64 2017-07-08 kinaba: } d335067c64 2017-07-08 kinaba: // END CUT HERE