f51ca8bd9d 2011-07-02 kinaba: #include <iostream> f51ca8bd9d 2011-07-02 kinaba: #include <sstream> f51ca8bd9d 2011-07-02 kinaba: #include <iomanip> f51ca8bd9d 2011-07-02 kinaba: #include <vector> f51ca8bd9d 2011-07-02 kinaba: #include <string> f51ca8bd9d 2011-07-02 kinaba: #include <map> f51ca8bd9d 2011-07-02 kinaba: #include <set> f51ca8bd9d 2011-07-02 kinaba: #include <algorithm> f51ca8bd9d 2011-07-02 kinaba: #include <numeric> f51ca8bd9d 2011-07-02 kinaba: #include <iterator> f51ca8bd9d 2011-07-02 kinaba: #include <functional> f51ca8bd9d 2011-07-02 kinaba: #include <complex> f51ca8bd9d 2011-07-02 kinaba: #include <queue> f51ca8bd9d 2011-07-02 kinaba: #include <stack> f51ca8bd9d 2011-07-02 kinaba: #include <cmath> f51ca8bd9d 2011-07-02 kinaba: #include <cassert> f51ca8bd9d 2011-07-02 kinaba: #include <cstring> f51ca8bd9d 2011-07-02 kinaba: using namespace std; f51ca8bd9d 2011-07-02 kinaba: typedef long long LL; f51ca8bd9d 2011-07-02 kinaba: typedef complex<double> CMP; f51ca8bd9d 2011-07-02 kinaba: f51ca8bd9d 2011-07-02 kinaba: class STable { public: f51ca8bd9d 2011-07-02 kinaba: string getString(string s, string t, long long pos) f51ca8bd9d 2011-07-02 kinaba: { f51ca8bd9d 2011-07-02 kinaba: const int S = s.size(); f51ca8bd9d 2011-07-02 kinaba: const int T = t.size(); f51ca8bd9d 2011-07-02 kinaba: vector< vector<LL> > len(S+1, vector<LL>(T+1)); f51ca8bd9d 2011-07-02 kinaba: for(int i=1; i<=S; ++i) f51ca8bd9d 2011-07-02 kinaba: len[i][0] = 1; f51ca8bd9d 2011-07-02 kinaba: for(int k=1; k<=T; ++k) f51ca8bd9d 2011-07-02 kinaba: len[0][k] = 1; f51ca8bd9d 2011-07-02 kinaba: for(int i=1; i<=S; ++i) f51ca8bd9d 2011-07-02 kinaba: for(int k=1; k<=T; ++k) f51ca8bd9d 2011-07-02 kinaba: len[i][k] = len[i-1][k] + len[i][k-1]; f51ca8bd9d 2011-07-02 kinaba: f51ca8bd9d 2011-07-02 kinaba: string ans; f51ca8bd9d 2011-07-02 kinaba: for(LL p=pos; p<min(pos+50, len[S][T]); ++p) f51ca8bd9d 2011-07-02 kinaba: ans += theChar(s, t, len, p, S, T); f51ca8bd9d 2011-07-02 kinaba: return ans; f51ca8bd9d 2011-07-02 kinaba: } f51ca8bd9d 2011-07-02 kinaba: f51ca8bd9d 2011-07-02 kinaba: char theChar(const string& s, const string & t, const vector< vector<LL> >& len, LL p, int i, int k) f51ca8bd9d 2011-07-02 kinaba: { f51ca8bd9d 2011-07-02 kinaba: if(i==0) f51ca8bd9d 2011-07-02 kinaba: return t[k-1]; f51ca8bd9d 2011-07-02 kinaba: if(k==0) f51ca8bd9d 2011-07-02 kinaba: return s[i-1]; f51ca8bd9d 2011-07-02 kinaba: f51ca8bd9d 2011-07-02 kinaba: if( early(s, t, i-1, k, i, k-1) ) f51ca8bd9d 2011-07-02 kinaba: if( p < len[i-1][k] ) f51ca8bd9d 2011-07-02 kinaba: return theChar(s,t,len,p,i-1,k); f51ca8bd9d 2011-07-02 kinaba: else f51ca8bd9d 2011-07-02 kinaba: return theChar(s,t,len,p-len[i-1][k],i,k-1); f51ca8bd9d 2011-07-02 kinaba: else f51ca8bd9d 2011-07-02 kinaba: if( p < len[i][k-1] ) f51ca8bd9d 2011-07-02 kinaba: return theChar(s,t,len,p,i,k-1); f51ca8bd9d 2011-07-02 kinaba: else f51ca8bd9d 2011-07-02 kinaba: return theChar(s,t,len,p-len[i][k-1],i-1,k); f51ca8bd9d 2011-07-02 kinaba: } f51ca8bd9d 2011-07-02 kinaba: f51ca8bd9d 2011-07-02 kinaba: bool early(const string& s, const string & t, int i, int k, int ii, int kk) f51ca8bd9d 2011-07-02 kinaba: { f51ca8bd9d 2011-07-02 kinaba: string le,ri; f51ca8bd9d 2011-07-02 kinaba: for(int x=0; x<i; ++x) le += s[x]; f51ca8bd9d 2011-07-02 kinaba: for(int x=0; x<k; ++x) le += t[x]; f51ca8bd9d 2011-07-02 kinaba: for(int x=0; x<ii; ++x) ri += s[x]; f51ca8bd9d 2011-07-02 kinaba: for(int x=0; x<kk; ++x) ri += t[x]; f51ca8bd9d 2011-07-02 kinaba: sort(le.begin(), le.end()); f51ca8bd9d 2011-07-02 kinaba: sort(ri.begin(), ri.end()); f51ca8bd9d 2011-07-02 kinaba: return le <= ri; f51ca8bd9d 2011-07-02 kinaba: } f51ca8bd9d 2011-07-02 kinaba: }; f51ca8bd9d 2011-07-02 kinaba: f51ca8bd9d 2011-07-02 kinaba: // BEGIN CUT HERE f51ca8bd9d 2011-07-02 kinaba: #include <ctime> f51ca8bd9d 2011-07-02 kinaba: double start_time; string timer() f51ca8bd9d 2011-07-02 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } f51ca8bd9d 2011-07-02 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) f51ca8bd9d 2011-07-02 kinaba: { os << "{ "; f51ca8bd9d 2011-07-02 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) f51ca8bd9d 2011-07-02 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } f51ca8bd9d 2011-07-02 kinaba: void verify_case(const string& Expected, const string& Received) { f51ca8bd9d 2011-07-02 kinaba: bool ok = (Expected == Received); f51ca8bd9d 2011-07-02 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; f51ca8bd9d 2011-07-02 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } f51ca8bd9d 2011-07-02 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); f51ca8bd9d 2011-07-02 kinaba: #define END verify_case(_, STable().getString(s, t, pos));} f51ca8bd9d 2011-07-02 kinaba: int main(){ f51ca8bd9d 2011-07-02 kinaba: f51ca8bd9d 2011-07-02 kinaba: CASE(0) f51ca8bd9d 2011-07-02 kinaba: string s = "ad"; f51ca8bd9d 2011-07-02 kinaba: string t = "cb"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 0LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "acbacd"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: CASE(1) f51ca8bd9d 2011-07-02 kinaba: string s = "fox"; f51ca8bd9d 2011-07-02 kinaba: string t = "cat"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 0LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "acfcfoacftacfcfocfox"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: CASE(2) f51ca8bd9d 2011-07-02 kinaba: string s = "Ra6b1t"; f51ca8bd9d 2011-07-02 kinaba: string t = "W0lf"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 66LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "RWab0RWRWa0RWl0RWRWa6RWa0RWRWa6RWa6RWab0RWRWa6RWa6"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: CASE(3) f51ca8bd9d 2011-07-02 kinaba: string s = "M0HAXG"; f51ca8bd9d 2011-07-02 kinaba: string t = "COFU12"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 919LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "MOFU2"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: CASE(4) f51ca8bd9d 2011-07-02 kinaba: string s = "a0B1c2D3e4F5gHiJkLmN"; f51ca8bd9d 2011-07-02 kinaba: string t = "A9b8C7d6EfGhIjKlMn"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 9876543210LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "B10AaB1c0Aa9Aa0AaB0AaB10AaB1c0AaB1c20Aa9Aa0AaB0Aa9"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: CASE(5) f51ca8bd9d 2011-07-02 kinaba: string s = "TCOR2"; f51ca8bd9d 2011-07-02 kinaba: string t = "MEDiUm"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 350LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "MTDEMTiCMTEMTDEMTDEMTiDEMTiUCMTEMTCMTOCMTEMTDEMTCM"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: CASE(6) f51ca8bd9d 2011-07-02 kinaba: string s = "b"; f51ca8bd9d 2011-07-02 kinaba: string t = "a"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 0LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "ab"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: CASE(6) f51ca8bd9d 2011-07-02 kinaba: string s = "b"; f51ca8bd9d 2011-07-02 kinaba: string t = "a"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 1LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "b"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: CASE(7) f51ca8bd9d 2011-07-02 kinaba: string s = "01234abcdefghijklmnopqrstuvwxyz"; f51ca8bd9d 2011-07-02 kinaba: string t = "56789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; f51ca8bd9d 2011-07-02 kinaba: long long pos = 999999999LL; f51ca8bd9d 2011-07-02 kinaba: string _ = "??"; f51ca8bd9d 2011-07-02 kinaba: END f51ca8bd9d 2011-07-02 kinaba: f51ca8bd9d 2011-07-02 kinaba: } f51ca8bd9d 2011-07-02 kinaba: // END CUT HERE