Overview
| SHA1 Hash: | 54a6dac9a883ff8cd7a58825fb090220b171dba6 |
|---|---|
| Date: | 2014-06-19 10:25:15 |
| User: | kinaba |
| Comment: | 625 |
| 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/625-U/1A.cpp version [f84ceb992b577020]
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 BuildingHeights { public: 23 + int minimum(vector <int> heights) 24 + { 25 + const int N = heights.size(); 26 + sort(heights.begin(), heights.end()); 27 + vector<int> sum(N+1); 28 + partial_sum(heights.begin(), heights.end(), sum.begin()+1); 29 + 30 + vector<int> A(N, 0x7fffffff); 31 + for(int s=0; s<N; ++s) 32 + for(int e=s+1; e<=N; ++e) 33 + { 34 + int M = e-s; 35 + int Max = heights[e-1]; 36 + int Sum = sum[e] - sum[s]; 37 + A[M-1] = min(A[M-1], Max*M-Sum); 38 + } 39 + 40 + int ans = 0; 41 + for(int a: A) ans ^= a; 42 + return ans; 43 + } 44 +}; 45 + 46 +// BEGIN CUT HERE 47 +#include <ctime> 48 +double start_time; string timer() 49 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 50 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 51 + { os << "{ "; 52 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 53 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 54 +void verify_case(const int& Expected, const int& Received) { 55 + bool ok = (Expected == Received); 56 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 57 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 58 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 59 +#define END verify_case(_, BuildingHeights().minimum(heights));} 60 +int main(){ 61 + 62 +CASE(0) 63 + int heights_[] = {1, 5, 4, 3, 8}; 64 + vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 65 + int _ = 22; 66 +END 67 +CASE(1) 68 + int heights_[] = {1, 2, 3}; 69 + vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 70 + int _ = 2; 71 +END 72 +CASE(2) 73 + int heights_[] = {3, 4, 1, 6, 8, 1}; 74 + vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 75 + int _ = 21; 76 +END 77 +CASE(3) 78 + int heights_[] = {990, 20, 2359, 1667, 51, 2455, 1659, 1093, 2015, 205, 656, 752, 1760, 1594, 857, 79 + 2033, 1868, 1932, 2408, 1518, 91, 2220, 1696, 1552, 933, 143, 1888, 1261, 2298, 1975, 80 + 929, 2139, 1994, 2139, 158, 896, 2093, 1816, 841, 459, 2020, 1496, 63, 131, 589, 919, 81 + 1015, 1308, 350, 922, 326, 1792, 641, 2021, 843, 425, 1015, 231, 1685, 2165, 1057, 82 + 1465, 655, 550, 1103, 812, 297, 2048, 1479, 1137, 6, 2350, 1484, 1420, 1332, 925, 2338, 83 + 1198, 2232, 1539, 2119, 57, 830, 1611, 929, 525, 888}; 84 + vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 85 + int _ = 56068; 86 +END 87 +/* 88 +CASE(4) 89 + int heights_[] = ; 90 + vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 91 + int _ = ; 92 +END 93 +CASE(5) 94 + int heights_[] = ; 95 + vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 96 + int _ = ; 97 +END 98 +*/ 99 +} 100 +// END CUT HERE
Added SRM/625-U/1B.cpp version [41fc1eb3d0bf2f33]
cannot compute difference between binary files
Added SRM/625-U/1C-U.cpp version [a9103b6d33af9248]
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 TreeColoring { public: 23 + long long color(int N, int Q, int startSeed, int threshold, int maxDist) 24 + { 25 + vector<int> parent(N-1), distance(N-1), queryType(Q), queryNode(Q); 26 + { 27 + int curValue = startSeed; 28 + function<int()> genNextRandom = [&]() { 29 + curValue = (curValue * 1999 + 17) % 1000003; 30 + return curValue; 31 + }; 32 + for(int i=0; i<N-1; i++) { 33 + distance[i] = genNextRandom() % maxDist; 34 + parent[i] = genNextRandom(); 35 + if (parent[i] < threshold) 36 + parent[i] = i; 37 + else 38 + parent[i] = parent[i] % (i + 1); 39 + } 40 + for (int i=0; i<Q; i++) { 41 + queryType[i] = genNextRandom() % 2 + 1; 42 + queryNode[i] = genNextRandom() % N; 43 + } 44 + } 45 + 46 + // Doubled parents for LCA and distance to the root 47 + const int INVALID = -1; 48 + vector<vector<int>> p(N, vector<int>(17, INVALID)); 49 + vector<int> d(N); 50 + for(int v=1; v<N; ++v) { 51 + p[v][1] = parent[v-1]; 52 + d[v] = d[p[v][1]] + distance[v-1]; 53 + } 54 + for(int d=2,k=2; k<17; d*=2,k++) 55 + for(int v=0; v<N; ++v) { 56 + int u = p[v][k-1]; 57 + if(u != INVALID) 58 + p[v][k] = p[u][k-1]; 59 + } 60 + 61 + return -1; 62 + } 63 +}; 64 + 65 +// BEGIN CUT HERE 66 +#include <ctime> 67 +double start_time; string timer() 68 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 69 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 70 + { os << "{ "; 71 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 72 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 73 +void verify_case(const long long& Expected, const long long& Received) { 74 + bool ok = (Expected == Received); 75 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 76 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 77 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 78 +#define END verify_case(_, TreeColoring().color(N, Q, startSeed, threshold, maxDist));} 79 +int main(){ 80 + 81 +CASE(0) 82 + int N = 4; 83 + int Q = 6; 84 + int startSeed = 15; 85 + int threshold = 2; 86 + int maxDist = 5; 87 + long long _ = 7LL; 88 +END 89 +CASE(1) 90 + int N = 4; 91 + int Q = 5; 92 + int startSeed = 2; 93 + int threshold = 9; 94 + int maxDist = 10; 95 + long long _ = 30LL; 96 +END 97 +CASE(2) 98 + int N = 8; 99 + int Q = 8; 100 + int startSeed = 3; 101 + int threshold = 5; 102 + int maxDist = 7; 103 + long long _ = 6LL; 104 +END 105 +CASE(3) 106 + int N = 14750; 107 + int Q = 50; 108 + int startSeed = 29750; 109 + int threshold = 1157; 110 + int maxDist = 21610; 111 + long long _ = 2537640LL; 112 +END 113 +CASE(4) 114 + int N = 100000; 115 + int Q = 100000; 116 + int startSeed = 123456; 117 + int threshold = 500000; 118 + int maxDist = 474747; 119 + long long _ = 726915029831LL; 120 +END 121 +CASE(5) 122 + int N = 100000; 123 + int Q = 100000; 124 + int startSeed = 654321; 125 + int threshold = 1000003; 126 + int maxDist = 1000003; 127 + long long _ = 562600687570528LL; 128 +END 129 +/* 130 +CASE(6) 131 + int N = ; 132 + int Q = ; 133 + int startSeed = ; 134 + int threshold = ; 135 + int maxDist = ; 136 + long long _ = LL; 137 +END 138 +CASE(7) 139 + int N = ; 140 + int Q = ; 141 + int startSeed = ; 142 + int threshold = ; 143 + int maxDist = ; 144 + long long _ = LL; 145 +END 146 +*/ 147 +} 148 +// END CUT HERE