Artifact Content
Not logged in

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