ADDED SRM/TCO15-2A/1A.cpp Index: SRM/TCO15-2A/1A.cpp ================================================================== --- SRM/TCO15-2A/1A.cpp +++ SRM/TCO15-2A/1A.cpp @@ -0,0 +1,112 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class ModModMod { public: + long long findSum(vector m, int R) + { + memo.assign(m.size()+1, -1); + return rec(m, 0, R); + } + + LL rec(const vector& m, int i, int R) + { + if(i == m.size()) + return LL(1+R)*R/2; + return rec_memod(m, i)*(R/m[i]) + rec(m, i+1, R%m[i]); + } + + vector memo; + LL rec_memod(const vector& m, int i) { + if(memo[i] >= 0) + return memo[i]; + return memo[i] = rec(m, i+1, m[i]-1); + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const long long& Expected, const long long& 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(_, ModModMod().findSum(m, R));} +int main(){ + +CASE(0) + int m_[] = {5,3,2}; + vector m(m_, m_+sizeof(m_)/sizeof(*m_)); + int R = 10; + long long _ = 4LL; +END +CASE(1) + int m_[] = {33, 15, 7, 10, 100, 9, 5}; + vector m(m_, m_+sizeof(m_)/sizeof(*m_)); + int R = 64; + long long _ = 92LL; +END +CASE(2) + int m_[] = {995,149,28,265,275,107,555,241,702,462,519,212,362,478,783,381,602,546,183,886,59,317,977,612,328,91,771,131}; + vector m(m_, m_+sizeof(m_)/sizeof(*m_)); + int R = 992363; + long long _ = 12792005LL; +END +CASE(3) + int m_[] = {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}; + vector m(m_, m_+sizeof(m_)/sizeof(*m_)); + int R = 100; + long long _ = 4950LL; +END +CASE(4) + int m_[] = {2934}; + vector m(m_, m_+sizeof(m_)/sizeof(*m_)); + int R = 10000000; + long long _ = 14664070144LL; +END +/* +CASE(5) + int m_[] = ; + vector m(m_, m_+sizeof(m_)/sizeof(*m_)); + int R = ; + long long _ = LL; +END +CASE(6) + int m_[] = ; + vector m(m_, m_+sizeof(m_)/sizeof(*m_)); + int R = ; + long long _ = LL; +END +*/ +} +// END CUT HERE ADDED SRM/TCO15-2A/1B-U.cpp Index: SRM/TCO15-2A/1B-U.cpp ================================================================== --- SRM/TCO15-2A/1B-U.cpp +++ SRM/TCO15-2A/1B-U.cpp @@ -0,0 +1,216 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +typedef int Vert; +typedef int Cost; +typedef pair Edge; +typedef vector Edges; +typedef vector Graph; + +class FoxMeeting { public: + int maxDistance(vector A, vector B, vector L, vector foxes) + { + // I hate 1-indexed numbering. + for(auto& ai: A) ai--; + for(auto& bi: B) bi--; + for(auto& fi: foxes) fi--; + + const int N = A.size()+1; + if(N==1) + return 0; + + Graph G(N); + for(int i=0; i Foxed(N, false); + for(int fi: foxes) + Foxed[fi] = true; + + int best = 0x7fffffff; + for(int C=0; C& Foxed) + { + int L=-1, R=5000000; // (L,R) + while(R-L>1) { + int C = (L+R)/2; + (can(G, Root, Foxed, C) ? R : L) = C; + } + return R; + } + + bool can(const Graph& G, int Root, const vector& Foxed, int MaxMove) { + enum State {FREE, MUSTBEFILLED, BAD}; + typedef pair> Result; + function rec; + rec = [&](Vert p, Vert v)->Result { + Cost parent_edge = 0; + bool must_fill = false; + vector reached; + for(auto& e: G[v]) + if(e.second != p) { + Result sr = rec(v, e.second); + if(sr.first == BAD) + return Result(BAD, vector()); + if(sr.first == MUSTBEFILLED) + must_fill = true; + reached.insert(reached.end(), sr.second.begin(), sr.second.end()); + } else { + parent_edge = e.first; + } + if(Foxed[v]) + reached.emplace_back(MaxMove); + + sort(reached.rbegin(), reached.rend()); + if(must_fill) { + if(reached.empty()) + return Result(BAD, vector()); + reached.pop_back(); + } + vector rr; + for(auto& ri: reached) + if(ri - parent_edge < 0) + must_fill = true; + else + rr.push_back(ri-parent_edge); + return Result(must_fill ? MUSTBEFILLED : FREE, rr); + }; + + Result r = rec(-1, Root); + return (r.first != BAD); + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& 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(_, FoxMeeting().maxDistance(A, B, L, foxes));} +int main(){ + +CASE(0) + int A_[] = {1}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int B_[] = {2}; + vector B(B_, B_+sizeof(B_)/sizeof(*B_)); + int L_[] = {5}; + vector L(L_, L_+sizeof(L_)/sizeof(*L_)); + int foxes_[] = {1, 2}; + vector foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); + int _ = 0; +END +CASE(1) + int A_[] = {1, 2}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int B_[] = {2, 3}; + vector B(B_, B_+sizeof(B_)/sizeof(*B_)); + int L_[] = {1, 1}; + vector L(L_, L_+sizeof(L_)/sizeof(*L_)); + int foxes_[] = {1, 3}; + vector foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); + int _ = 1; +END +CASE(2) + int A_[] = {1, 2}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int B_[] = {2, 3}; + vector B(B_, B_+sizeof(B_)/sizeof(*B_)); + int L_[] = {1, 1}; + vector L(L_, L_+sizeof(L_)/sizeof(*L_)); + int foxes_[] = {1, 2, 3}; + vector foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); + int _ = 0; +END +CASE(3) + int A_[] = {10,8,3,7,2,6,9,1,4}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int B_[] = {5,5,8,10,5,5,6,10,3}; + vector B(B_, B_+sizeof(B_)/sizeof(*B_)); + int L_[] = {71846,10951,42265,37832,29439,95676,83661,28186,21216}; + vector L(L_, L_+sizeof(L_)/sizeof(*L_)); + int foxes_[] = {1,2,3,4,5,6,7,8,9,10}; + vector foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); + int _ = 0; +END +CASE(4) + int A_[] = {8,15,22,24,2,25,13,26,18,4,9,29,1,12,3,16,14,21,19,27,17,7,20,10,30,11,6,5,23}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int B_[] = {28,28,8,8,28,28,25,2,13,24,24,22,22,29,4,22,8,4,1,24,21,14,18,16,13,21,14,1,25}; + vector B(B_, B_+sizeof(B_)/sizeof(*B_)); + int L_[] = {79374,40629,43195,73589,24200,63937,35339,7598,65109,51764,11142,84017,51078,58051,81387,22035,34883,92710,52283,57337,79309,3383,41904,35839,38242,43208,82062,24676,71838}; + vector L(L_, L_+sizeof(L_)/sizeof(*L_)); + int foxes_[] = {3,5,7,9,10,14,17,19,20,21,24,25,28}; + vector foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); + int _ = 107013; +END +CASE(5) + int A_[] = {34,14,22,9,24,19,11,37,33,21,5,30,1,43,7,31,45,27,6,12,13,35,23,47,49,50,26,40,16,10,48,25,29,15,28,46,4,20,44,17,39,32,38,2,42,8,36,3,41}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int B_[] = {18,18,18,14,9,34,9,24,34,11,18,14,21,21,43,1,22,7,1,30,14,33,13,18,9,5,1,1,26,19,50,33,50,40,29,48,50,37,16,40,48,14,30,22,47,37,7,50,6}; + vector B(B_, B_+sizeof(B_)/sizeof(*B_)); + int L_[] = {22051,11109,85275,6691,43705,47374,27748,5411,62549,84079,89542,38006,82198,24083,16847,66335,3542,72495,37378,73973,85703,51682,68688,94295,31337, +90071,99317,63484,43244,99079,55857,34503,79709,82140,91137,27033,91599,61168,52345,49569,58919,38133,43361, +40718,2115,79278,88841,40966,42023}; + vector L(L_, L_+sizeof(L_)/sizeof(*L_)); + int foxes_[] = {5,12,13,18,23,27,28,29,32,33,34,35,36,37,40,42,43,47,48,49,50}; + vector foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); + int _ = 89342; +END +/* +CASE(6) + int A_[] = ; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int B_[] = ; + vector B(B_, B_+sizeof(B_)/sizeof(*B_)); + int L_[] = ; + vector L(L_, L_+sizeof(L_)/sizeof(*L_)); + int foxes_[] = ; + vector foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); + int _ = ; +END +CASE(7) + int A_[] = ; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int B_[] = ; + vector B(B_, B_+sizeof(B_)/sizeof(*B_)); + int L_[] = ; + vector L(L_, L_+sizeof(L_)/sizeof(*L_)); + int foxes_[] = ; + vector foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); + int _ = ; +END +*/ +} +// END CUT HERE