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