Overview
| SHA1 Hash: | b3c7c622f48ea13088cb5b72f6e277a174c0ce4c |
|---|---|
| Date: | 2015-12-18 14:45:32 |
| User: | kinaba |
| Comment: | 675 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/675-U/1A.cpp version [a79c22b01124d1da]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TreeAndPathLength3 { public: > 23 vector <int> construct(int s) > 24 { > 25 if(s == 1) { > 26 int ans[] = {0, 1, 1, 2, 2, 3}; > 27 return vector<int>(ans+0, ans+6); > 28 } > 29 > 30 // . - . - . - . -.-. > 31 // n nodes -.-. > 32 // -.-. > 33 // -.-. k branches > 34 // = > 35 // (n-3) + k + k + k(k-1) > 36 > 37 int k=0; > 38 for(; k+k+k*(k-1)<=s; ++k) {} > 39 --k; > 40 int n = s - k - k - k*(k-1) + 3; > 41 > 42 vector<int> edges; > 43 for(int v=0; v<n-1; ++v) { > 44 edges.emplace_back(v); > 45 edges.emplace_back(v+1); > 46 } > 47 for(int u=0; u<k; ++u) { > 48 edges.emplace_back(n-1); > 49 edges.emplace_back(n+u); > 50 edges.emplace_back(n+u); > 51 edges.emplace_back(n+u+k); > 52 } > 53 return edges; > 54 } > 55 }; > 56 > 57 // BEGIN CUT HERE > 58 #include <ctime> > 59 double start_time; string timer() > 60 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 61 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 62 { os << "{ "; > 63 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 64 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 65 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 66 bool ok = (Expected == Received); > 67 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 68 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 69 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 70 #define END verify_case(_, TreeAndPathLength3().construct(s));} > 71 int main(){ > 72 > 73 CASE(0) > 74 int s = 1; > 75 int __[] = {0, 1, 1, 2, 2, 3 }; > 76 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 77 END > 78 CASE(1) > 79 int s = 2; > 80 int __[] = {0, 1, 1, 2, 2, 3, 3, 4 }; > 81 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 82 END > 83 CASE(2) > 84 int s = 6; > 85 int __[] = {0, 1, 1, 2, 0, 3, 3, 4, 0, 5, 5, 6 }; > 86 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 87 END > 88 CASE(3) > 89 int s = 8; > 90 int __[] = {0, 1, 1, 2, 1, 3, 3, 4, 3, 5, 5, 6, 5, 7 }; > 91 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 92 END > 93 CASE(4) > 94 int s = 10000; > 95 int __[] = {1}; > 96 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 97 END > 98 /* > 99 CASE(5) > 100 int s = ; > 101 int __[] = ; > 102 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 103 END > 104 */ > 105 } > 106 // END CUT HERE
Added SRM/675-U/1B.cpp version [5185ebfd818bdb8a]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class LimitedMemorySeries1 { public: > 23 long long getSum(int n, int x0, int a, int b, const vector <int>& query) > 24 { > 25 LL sum = 0; > 26 multiset<int> qq(query.begin(), query.end()); > 27 > 28 const int BACKET = min(n, 250000); > 29 int prev_turn_largest = -1; > 30 int ptl_count = 0; > 31 > 32 int* pq = new int[BACKET+1]; > 33 int pql = 0; > 34 > 35 for(int s=0; s<n; s+=BACKET) { > 36 pql = 0; // PQ keeping min BACKET elements > 37 > 38 int v = x0; > 39 for(int i=0; i<n; ++i) { > 40 if(v < prev_turn_largest) {} > 41 else if(v == prev_turn_largest && ptl_count>0) { > 42 else { > 43 pq[pql++]=v; push_heap(pq+0, pq+pql); > 44 if(pql>BACKET) > 45 pop_heap(pq+0, pq+pql), pql--; / > 46 } > 47 v = int((LL(v) * a + b) % 1000000007); > 48 } > 49 int cur_largest = -1; > 50 int cl_count = 0; > 51 > 52 for(int rank=s+pql-1; rank>=s; --rank) { > 53 int v = pq[0]; > 54 pop_heap(pq+0, pq+pql), pql--; > 55 > 56 if(cur_largest < v) cur_largest = v, cl_count = > 57 else if(cur_largest == v) cl_count++; > 58 > 59 if(qq.count(rank)) { > 60 sum += LL(v) * qq.count(rank); > 61 qq.erase(rank); > 62 } > 63 } > 64 > 65 prev_turn_largest = cur_largest; > 66 ptl_count = cl_count; > 67 } > 68 delete[] pq; > 69 return sum; > 70 } > 71 }; > 72 > 73 // BEGIN CUT HERE > 74 #include <ctime> > 75 double start_time; string timer() > 76 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 77 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 78 { os << "{ "; > 79 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 80 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 81 void verify_case(const long long& Expected, const long long& Received) { > 82 bool ok = (Expected == Received); > 83 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 84 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 85 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 86 #define END verify_case(_, LimitedMemorySeries1().getSum(n, x0, a, b, query > 87 int main(){ > 88 > 89 CASE(0) > 90 int n = 5; > 91 int x0 = 100; > 92 int a = 1; > 93 int b = 5; > 94 int query_[] = {0,3}; > 95 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 96 long long _ = 215LL; > 97 END > 98 CASE(1) > 99 int n = 5; > 100 int x0 = 123456789; > 101 int a = 987654321; > 102 int b = 1000000006; > 103 int query_[] = {0,1,2,3}; > 104 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 105 long long _ = 733028692LL; > 106 END > 107 CASE(2) > 108 int n = 5000000; > 109 int x0 = 482995837; > 110 int a = 512849030; > 111 int b = 120583724; > 112 int query_[] = {4854010,3139503,1855546,219904,846357,2624639,891260,217 > 113 3848272,2062765,2922407,4850301,1279972,4929307,2035456,3562859,1749594,4089499 > 114 1650805,1245213,3020379,4661668,427170,1176815,292944,2435328,420809,4170355,26 > 115 4311718,2098572,4868054,30319,4588969,1460677,1335028,3921495,3621970,4459335,9 > 116 2316560,1634961,2280624,1940395,3321546,3168811,1856547,3859093,4340475,1382782 > 117 185008,1135373,2821050,3260484,4821220,1700954,3243343,2183615,394339,2630121,1 > 118 3898314,892312,2015580,11161,4965095,2128470,2320933,1095881,3938450,1887098,97 > 119 1145560,2894728,1026181,3259403,4509345,3610224,3584456,1877483,2665752,2243671 > 120 1471925,4144568}; > 121 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 122 long long _ = 49684994148LL; > 123 END > 124 CASE(2) > 125 int n = 5000000; > 126 int x0 = 482995837; > 127 int a = 512849030; > 128 int b = 120583724; > 129 int query_[] = {5000000,4999999,4999998,4999997,4999996,4999995,4999994, > 130 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 131 long long _ = -1LL; > 132 END > 133 /* > 134 CASE(3) > 135 int n = ; > 136 int x0 = ; > 137 int a = ; > 138 int b = ; > 139 int query_[] = ; > 140 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 141 long long _ = LL; > 142 END > 143 CASE(4) > 144 int n = ; > 145 int x0 = ; > 146 int a = ; > 147 int b = ; > 148 int query_[] = ; > 149 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 150 long long _ = LL; > 151 END > 152 */ > 153 } > 154 // END CUT HERE