ed7454da2a 2016-10-26 kinaba: #include <iostream> ed7454da2a 2016-10-26 kinaba: #include <sstream> ed7454da2a 2016-10-26 kinaba: #include <iomanip> ed7454da2a 2016-10-26 kinaba: #include <vector> ed7454da2a 2016-10-26 kinaba: #include <string> ed7454da2a 2016-10-26 kinaba: #include <map> ed7454da2a 2016-10-26 kinaba: #include <set> ed7454da2a 2016-10-26 kinaba: #include <algorithm> ed7454da2a 2016-10-26 kinaba: #include <numeric> ed7454da2a 2016-10-26 kinaba: #include <iterator> ed7454da2a 2016-10-26 kinaba: #include <functional> ed7454da2a 2016-10-26 kinaba: #include <complex> ed7454da2a 2016-10-26 kinaba: #include <queue> ed7454da2a 2016-10-26 kinaba: #include <stack> ed7454da2a 2016-10-26 kinaba: #include <cmath> ed7454da2a 2016-10-26 kinaba: #include <cassert> ed7454da2a 2016-10-26 kinaba: #include <tuple> ed7454da2a 2016-10-26 kinaba: using namespace std; ed7454da2a 2016-10-26 kinaba: typedef long long LL; ed7454da2a 2016-10-26 kinaba: typedef complex<double> CMP; ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: string S; ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: class KthStringAgain { ed7454da2a 2016-10-26 kinaba: public: ed7454da2a 2016-10-26 kinaba: struct Cand { ed7454da2a 2016-10-26 kinaba: // represents ALL(S[perm_head..$]) S[tail_mask]^r ed7454da2a 2016-10-26 kinaba: int perm_head; ed7454da2a 2016-10-26 kinaba: string tail; ed7454da2a 2016-10-26 kinaba: LL num; ed7454da2a 2016-10-26 kinaba: Cand(int p, const string& t, LL n=1) : perm_head(p), tail(t), num(n) {} ed7454da2a 2016-10-26 kinaba: LL count() const { return (1LL << (S.size() - perm_head))*num; } ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: bool operator<(const Cand& rhs) const { ed7454da2a 2016-10-26 kinaba: if (perm_head != rhs.perm_head) return perm_head < rhs.perm_head; ed7454da2a 2016-10-26 kinaba: return tail < rhs.tail; ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: bool operator==(const Cand& rhs) const { ed7454da2a 2016-10-26 kinaba: if (perm_head != rhs.perm_head) return false; ed7454da2a 2016-10-26 kinaba: return tail == rhs.tail; ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: }; ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: string getKth(string s, long long k) { ed7454da2a 2016-10-26 kinaba: S = s; ed7454da2a 2016-10-26 kinaba: vector<Cand> cc(1, Cand(0, string())); ed7454da2a 2016-10-26 kinaba: return findKthAmong(cc, k - 1); ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: string findKthAmong(vector<Cand>& c, LL k) { ed7454da2a 2016-10-26 kinaba: sort(c.begin(), c.end()); ed7454da2a 2016-10-26 kinaba: for(int i=c.size()-1; i>=1; --i) ed7454da2a 2016-10-26 kinaba: if (c[i] == c[i - 1]) { ed7454da2a 2016-10-26 kinaba: c[i - 1].num += c[i].num; ed7454da2a 2016-10-26 kinaba: c[i].num = 0; ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: map<char, vector<Cand>> next; ed7454da2a 2016-10-26 kinaba: for (const Cand& cc : c) { ed7454da2a 2016-10-26 kinaba: if (cc.num == 0) ed7454da2a 2016-10-26 kinaba: continue; ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: if (cc.perm_head == S.size()) { ed7454da2a 2016-10-26 kinaba: if (cc.tail.empty()) ed7454da2a 2016-10-26 kinaba: return ""; //? ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: next[cc.tail[0]].emplace_back(cc.perm_head, cc.tail.substr(1), cc.num); ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: else { ed7454da2a 2016-10-26 kinaba: for (int i = cc.perm_head; i < S.size(); ++i) { ed7454da2a 2016-10-26 kinaba: string t2 = S.substr(cc.perm_head, i - cc.perm_head); ed7454da2a 2016-10-26 kinaba: reverse(t2.begin(), t2.end()); ed7454da2a 2016-10-26 kinaba: t2 += cc.tail; ed7454da2a 2016-10-26 kinaba: next[S[i]].emplace_back(i + 1, t2, cc.num * (i+1==S.size() ? 2 : 1)); ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: LL off = 0; ed7454da2a 2016-10-26 kinaba: for (auto&& kv : next) { ed7454da2a 2016-10-26 kinaba: LL num = 0; ed7454da2a 2016-10-26 kinaba: for (auto&& vv : kv.second) ed7454da2a 2016-10-26 kinaba: num += vv.count(); ed7454da2a 2016-10-26 kinaba: if (off <= k && k < off + num) { ed7454da2a 2016-10-26 kinaba: return kv.first + findKthAmong(kv.second, k - off); ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: off += num; ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: assert(false); ed7454da2a 2016-10-26 kinaba: return "WRONG ANSWER"; ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: }; ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: // BEGIN CUT HERE ed7454da2a 2016-10-26 kinaba: #include <ctime> ed7454da2a 2016-10-26 kinaba: double start_time; string timer() ed7454da2a 2016-10-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ed7454da2a 2016-10-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) ed7454da2a 2016-10-26 kinaba: { os << "{ "; ed7454da2a 2016-10-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) ed7454da2a 2016-10-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } ed7454da2a 2016-10-26 kinaba: void verify_case(const string& Expected, const string& Received) { ed7454da2a 2016-10-26 kinaba: bool ok = (Expected == Received); ed7454da2a 2016-10-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; ed7454da2a 2016-10-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } ed7454da2a 2016-10-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); ed7454da2a 2016-10-26 kinaba: #define END verify_case(_, KthStringAgain().getKth(s, k));} ed7454da2a 2016-10-26 kinaba: int main(){ ed7454da2a 2016-10-26 kinaba: ed7454da2a 2016-10-26 kinaba: CASE(0) ed7454da2a 2016-10-26 kinaba: string s = "xyz"; ed7454da2a 2016-10-26 kinaba: long long k = 5LL; ed7454da2a 2016-10-26 kinaba: string _ = "yzx"; ed7454da2a 2016-10-26 kinaba: END ed7454da2a 2016-10-26 kinaba: CASE(1) ed7454da2a 2016-10-26 kinaba: string s = "abc"; ed7454da2a 2016-10-26 kinaba: long long k = 1LL; ed7454da2a 2016-10-26 kinaba: string _ = "abc"; ed7454da2a 2016-10-26 kinaba: END ed7454da2a 2016-10-26 kinaba: CASE(2) ed7454da2a 2016-10-26 kinaba: string s = "abc"; ed7454da2a 2016-10-26 kinaba: long long k = 8LL; ed7454da2a 2016-10-26 kinaba: string _ = "cba"; ed7454da2a 2016-10-26 kinaba: END ed7454da2a 2016-10-26 kinaba: CASE(3) ed7454da2a 2016-10-26 kinaba: string s = "topcoder"; ed7454da2a 2016-10-26 kinaba: long long k = 58LL; ed7454da2a 2016-10-26 kinaba: string _ = "ooredcpt"; ed7454da2a 2016-10-26 kinaba: END ed7454da2a 2016-10-26 kinaba: CASE(4) ed7454da2a 2016-10-26 kinaba: string s = "aaaabcdeeeghhhhhiijjjkllmmooooqqrrrrssttuuvvvvvwyy"; ed7454da2a 2016-10-26 kinaba: long long k = 38517901796974LL; ed7454da2a 2016-10-26 kinaba: string _ = "aaaacdeehhhijklmmqqrsttvvvvwyyvuusrrrooooljjihhgeb"; ed7454da2a 2016-10-26 kinaba: END ed7454da2a 2016-10-26 kinaba: CASE(5) ed7454da2a 2016-10-26 kinaba: string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; ed7454da2a 2016-10-26 kinaba: long long k = 1234567890LL; ed7454da2a 2016-10-26 kinaba: string _ = "???????"; ed7454da2a 2016-10-26 kinaba: END ed7454da2a 2016-10-26 kinaba: /* ed7454da2a 2016-10-26 kinaba: CASE(6) ed7454da2a 2016-10-26 kinaba: string s = ; ed7454da2a 2016-10-26 kinaba: long long k = LL; ed7454da2a 2016-10-26 kinaba: string _ = ; ed7454da2a 2016-10-26 kinaba: END ed7454da2a 2016-10-26 kinaba: */ ed7454da2a 2016-10-26 kinaba: } ed7454da2a 2016-10-26 kinaba: // END CUT HERE