Overview
| SHA1 Hash: | 8166493378a31f7bca82e13cd8845502882b359c |
|---|---|
| Date: | 2012-05-12 15:05:07 |
| User: | kinaba |
| Comment: | 541 |
| 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/541-U/1A.cpp version [0df8f7ff2403d0f5]
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 <cstring> 18 +#ifdef __GNUC__ 19 +#include <ext/hash_map> 20 +#define unordered_map __gnu_cxx::hash_map 21 +#else 22 +#include <unordered_map> 23 +#endif 24 +using namespace std; 25 +typedef long long LL; 26 +typedef complex<double> CMP; 27 + 28 +class AntsMeet { public: 29 + int countAnts(vector <int> x, vector <int> y, string direction) 30 + { 31 + const int N = x.size(); 32 + 33 + map< int, vector< pair<int,int> > > bye; 34 + for(int i=0; i<N; ++i) 35 + for(int j=i+1; j<N; ++j) { 36 + int t; 37 + if( meet(x[i], y[i], direction[i], x[j], y[j], direction[j], &t) ) 38 + bye[t].push_back(make_pair(i,j)); 39 + } 40 + 41 + set<int> dead; 42 + for(map<int, vector< pair<int,int> > >::iterator it=bye.begin(); it!=bye.end(); ++it) { 43 + set<int> die; 44 + vector< pair<int,int> >& events = it->second; 45 + for(int i=0; i<events.size(); ++i) { 46 + int a = events[i].first; 47 + int b = events[i].second; 48 + if( dead.count(a)==0 && dead.count(b)==0 ) { 49 + die.insert(a); 50 + die.insert(b); 51 +// dead.insert(a); 52 + // dead.insert(b); 53 + } 54 + } 55 + dead.insert(die.begin(), die.end()); 56 + } 57 + 58 + return N - dead.size(); 59 + } 60 + 61 + bool meet(int x, int y, char d, int X, int Y, int D, int* t) 62 + { 63 + if( d == D ) 64 + return false; 65 + int dx = dx_of(d); 66 + int dy = dy_of(d); 67 + int DX = dx_of(D); 68 + int DY = dy_of(D); 69 + 70 + int tx; 71 + if( !meet(x, dx, X, DX, &tx) ) 72 + return false; 73 + int ty; 74 + if( !meet(y, dy, Y, DY, &ty) ) 75 + return false; 76 + *t = (tx==-1 ? ty : tx); 77 + return (tx==ty || tx==-1 || ty==-1); 78 + } 79 + 80 + bool meet(int x, int dx, int X, int DX, int* t) 81 + { 82 + if( x==X && dx==DX ) { 83 + *t = -1; 84 + return true; 85 + } else if( dx==DX ) { 86 + return false; 87 + } else { 88 + *t = (x-X)*2 / (DX-dx); 89 + return ( *t >= 0 ); 90 + } 91 + } 92 + 93 + int dx_of(char d) 94 + { 95 + if(d=='E') return +1; 96 + if(d=='W') return -1; 97 + return 0; 98 + } 99 + 100 + int dy_of(char d) 101 + { 102 + if(d=='N') return +1; 103 + if(d=='S') return -1; 104 + return 0; 105 + } 106 +}; 107 + 108 +// BEGIN CUT HERE 109 +#include <ctime> 110 +double start_time; string timer() 111 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 112 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 113 + { os << "{ "; 114 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 115 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 116 +void verify_case(const int& Expected, const int& Received) { 117 + bool ok = (Expected == Received); 118 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 119 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 120 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 121 +#define END verify_case(_, AntsMeet().countAnts(x, y, direction));} 122 +int main(){ 123 + 124 +CASE(0) 125 + int x_[] = {0,10,20,30}; 126 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 127 + int y_[] = {0,10,20,30}; 128 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 129 + string direction = "NWNE"; 130 + int _ = 2; 131 +END 132 +CASE(1) 133 + int x_[] = {-10,0,0,10}; 134 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 135 + int y_[] = {0,-10,10,0}; 136 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 137 + string direction = "NEWS"; 138 + int _ = 0; 139 +END 140 +CASE(2) 141 + int x_[] = {-1,-1,-1,0,0,0,1,1,1}; 142 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 143 + int y_[] = {-1,0,1,-1,0,1,-1,0,1}; 144 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 145 + string direction = "ESEWNNEWW"; 146 + int _ = 4; 147 +END 148 +CASE(3) 149 + int x_[] = {4,7,6,2,6,5,7,7,8,4,7,8,8,8,5,4,8,9,1,5,9,3,4,0,0,1,0,7,2,6,9,6,3,0,5,5,1,2,0,4,9,7,7,1,8,1,9,2,7,3}; 150 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 151 + int y_[] = {2,3,0,6,8,4,9,0,5,0,2,4,3,8,1,5,0,7,3,7,0,9,8,1,9,4,7,8,1,1,6,6,6,2,8,5,1,9,0,1,1,1,7,0,2,5,4,7,5,3}; 152 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 153 + string direction = "SSNWSWSENSWSESWEWSWSENWNNNESWSWSWWSSWEEWWNWWWNWENN" ; 154 + int _ = 25; 155 +END 156 +CASE(4) 157 + int x_[] = {478,-664,759,434,-405,513,565,-396,311,-174,56,993,251,-341,993,-112,242,129,383,513,-78,-341,-148,129,423 158 +,493,434,-405,478,-148,929,251,56,242,929,-78,423,-664,802,251,759,383,-112,-591,-591,-248,660,660,735,493}; 159 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 160 + int y_[] = {-186,98,948,795,289,-678,948,-170,-195,290,-354,-424,289,-157,-166,150,706,-678,684,-294,-234,36,36,-294,-216 161 +,-234,427,945,265,-157,265,715,275,715,-186,337,798,-170,427,706,754,961,286,-216,798,286,961,684,-424,337}; 162 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 163 + string direction = "WNSNNSSWWWEENWESNSWSWSEWWEWEWWWNWESNSSNNSNNWWWNESE"; 164 + int _ = 44; 165 +END 166 +CASE(5) 167 + int x_[] = {0, 1, 0, 10, 9, 11}; 168 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 169 + int y_[] = {0, 1, 2, 10, 11, 11}; 170 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 171 + string direction = "NWSNES"; 172 + int _ = 0; 173 +END 174 +/* 175 +CASE(6) 176 + int x_[] = ; 177 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 178 + int y_[] = ; 179 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 180 + string direction = ; 181 + int _ = ; 182 +END 183 +*/ 184 +} 185 +// END CUT HERE
Added SRM/541-U/1B.cpp version [31dfe136aa2ce7ba]
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 <cstring> 18 +#ifdef __GNUC__ 19 +#include <ext/hash_map> 20 +#define unordered_map __gnu_cxx::hash_map 21 +#else 22 +#include <unordered_map> 23 +#endif 24 +using namespace std; 25 +typedef long long LL; 26 +typedef complex<double> CMP; 27 + 28 +static const int MODVAL = 1000000007; 29 + 30 +class AkariDaisukiDiv1 { public: 31 + int countF(string W, string A, string D, string S, string F, int k) 32 + { 33 + string X = S; 34 + 35 + while(k>0 && X.size()<=F.size()) { 36 + X = W + X + A + X + D; 37 + --k; 38 + } 39 + 40 + int Usushio = naive(X, F, 0, X.size()); 41 + if( k == 0 ) 42 + return Usushio; 43 + 44 + string WW = "", DD=""; 45 + for(int n=0,a,b,c; n<k; ++n) { 46 + if( n <= 50 ) { 47 + b = naive(X+DD+A+WW+X, F, X.size()+DD.size()-F.size()+1, X.size()+DD.size()+A.size()); 48 + WW += W; 49 + DD += D; 50 + a = naive(WW+X, F, 0, W.size()); 51 + c = naive(X+DD, F, X.size()+DD.size()-D.size()-F.size()+1, X.size()+DD.size()); 52 + } 53 + Usushio = (Usushio*2 + a+b+c) % MODVAL; 54 + } 55 + return Usushio; 56 + } 57 + 58 + int naive(const string& X, const string& F, int S, int E) 59 + { 60 + int cnt = 0; 61 + for(int i=0; i+F.size()<=X.size(); ++i) 62 + if( S<=i && i<E ) 63 + if( equal(X.begin()+i, X.begin()+i+F.size(), F.begin()) ) 64 + ++cnt; 65 + return cnt; 66 + } 67 +}; 68 + 69 +// BEGIN CUT HERE 70 +#include <ctime> 71 +double start_time; string timer() 72 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 73 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 74 + { os << "{ "; 75 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 76 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 77 +void verify_case(const int& Expected, const int& Received) { 78 + bool ok = (Expected == Received); 79 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 80 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 81 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 82 +#define END verify_case(_, AkariDaisukiDiv1().countF(Waai, Akari, Daisuki, S, F, k));} 83 +int main(){ 84 + 85 +CASE(0) 86 + string Waai = "a"; 87 + string Akari = "b"; 88 + string Daisuki = "c"; 89 + string S = "x"; 90 + string F = "axb"; 91 + int k = 2; 92 + int _ = 2; 93 +END 94 +CASE(1) 95 + string Waai = "a"; 96 + string Akari = "b"; 97 + string Daisuki = "c"; 98 + string S = "x"; 99 + string F = "abcdefghij"; 100 + int k = 1; 101 + int _ = 0; 102 +END 103 +CASE(2) 104 + string Waai = "a"; 105 + string Akari = "a"; 106 + string Daisuki = "a"; 107 + string S = "b"; 108 + string F = "aba"; 109 + int k = 2; 110 + int _ = 4; 111 +END 112 +CASE(3) 113 + string Waai = "a"; 114 + string Akari = "b"; 115 + string Daisuki = "c"; 116 + string S = "d"; 117 + string F = "baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba"; 118 + int k = 58; 119 + int _ = 191690599; 120 +END 121 +CASE(4) 122 + string Waai = "a"; 123 + string Akari = "x"; 124 + string Daisuki = "y"; 125 + string S = "b"; 126 + string F = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; 127 + int k = 49; 128 + int _ = 1; 129 +END 130 +CASE(5) 131 + string Waai = "waai"; 132 + string Akari = "akari"; 133 + string Daisuki = "daisuki"; 134 + string S = "usushio"; 135 + string F = "id"; 136 + int k = 10000000; 137 + int _ = 127859200; 138 +END 139 +CASE(6) 140 + string Waai = "vfsebgjfyfgerkqlr"; 141 + string Akari = "ezbiwls"; 142 + string Daisuki = "kjerx"; 143 + string S = "jbmjvaawoxycfndukrjfg"; 144 + string F = "bgjfyfgerkqlrvfsebgjfyfgerkqlrvfsebgjfyfgerkqlrvfs"; 145 + int k = 1575724; 146 + int _ = 483599313; 147 +END 148 +/* 149 +CASE(7) 150 + string Waai = ; 151 + string Akari = ; 152 + string Daisuki = ; 153 + string S = ; 154 + string F = ; 155 + int k = ; 156 + int _ = ; 157 +END 158 +CASE(8) 159 + string Waai = ; 160 + string Akari = ; 161 + string Daisuki = ; 162 + string S = ; 163 + string F = ; 164 + int k = ; 165 + int _ = ; 166 +END 167 +*/ 168 +} 169 +// END CUT HERE
Deleted SRM/TCO12-1/1A.cpp version [5b4985a0bbd0b903]
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 <cstring> 18 -#ifdef __GNUC__ 19 -#include <ext/hash_map> 20 -#define unordered_map __gnu_cxx::hash_map 21 -#else 22 -#include <unordered_map> 23 -#endif 24 -using namespace std; 25 -typedef long long LL; 26 -typedef complex<double> CMP; 27 - 28 -class EllysJuice { public: 29 - vector <string> getWinners(vector <string> players) 30 - { 31 - set<string> winners; 32 - 33 - sort(players.begin(), players.end()); 34 - do 35 - winners.insert( play(players) ); 36 - while( next_permutation(players.begin(), players.end()) ); 37 - 38 - winners.erase(""); 39 - return vector<string>(winners.begin(), winners.end()); 40 - } 41 - 42 - string play(const vector<string>& p) 43 - { 44 - int juice[2] = {65536, 65536}; 45 - map<string, int> total; 46 - for(int i=0; i<p.size(); ++i) 47 - total[p[i]] += (juice[i%2]/=2); 48 - 49 - string best_name; 50 - int best = 0; 51 - bool tie = false; 52 - for(map<string, int>::iterator it=total.begin(); it!=total.end(); ++it) 53 - if( it->second > best ) { 54 - best_name = it->first; 55 - best = it->second; 56 - tie = false; 57 - } 58 - else if( it->second == best ) 59 - tie = true; 60 - return tie ? "" : best_name; 61 - } 62 -}; 63 - 64 -// BEGIN CUT HERE 65 -#include <ctime> 66 -double start_time; string timer() 67 - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 68 -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 69 - { os << "{ "; 70 - for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 71 - os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 72 -void verify_case(const vector <string>& Expected, const vector <string>& Received) { 73 - bool ok = (Expected == Received); 74 - if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 75 - cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 76 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 77 -#define END verify_case(_, EllysJuice().getWinners(players));} 78 -int main(){ 79 - 80 -CASE(0) 81 - string players_[] = { "elly", "kriss", "stancho", "elly", "stancho" }; 82 - vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_)); 83 - string __[] = {"elly", "stancho" }; 84 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 85 -END 86 -CASE(1) 87 - string players_[] = {"torb", "elly", "stancho", "kriss"}; 88 - vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_)); 89 - vector <string> _; 90 -END 91 -CASE(2) 92 - string players_[] = {"elly", "elly", "elly", "elly", "elly"}; 93 - vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_)); 94 - string __[] = {"elly" }; 95 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 96 -END 97 -CASE(3) 98 - string players_[] = { "ariadne", "elly", "ariadne", "stancho", "stancho", "kriss", "stancho", "elly" }; 99 - vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_)); 100 - string __[] = {"ariadne", "elly", "stancho" }; 101 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 102 -END 103 -CASE(4) 104 - string players_[] = {"b","b","a","a"}; 105 - vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_)); 106 - string __[] = {"a","b"}; 107 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 108 -END 109 -/* 110 -CASE(5) 111 - string players_[] = ; 112 - vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_)); 113 - string __[] = ; 114 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 115 -END 116 -*/ 117 -} 118 -// END CUT HERE
Deleted SRM/TCO12-1/1B.cpp version [ada6668a1964faea]
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 <cstring> 18 -#ifdef __GNUC__ 19 -#include <ext/hash_map> 20 -#define unordered_map __gnu_cxx::hash_map 21 -#else 22 -#include <unordered_map> 23 -#endif 24 -using namespace std; 25 -typedef long long LL; 26 -typedef complex<double> CMP; 27 - 28 -class EllysFractions { public: 29 - long long getCount(int N) 30 - { 31 - LL total = 0; 32 - for(int k=2; k<=N; ++k) 33 - total += getExact(k); 34 - return total; 35 - } 36 - 37 - LL getExact(int N) 38 - { 39 - int np = 0; 40 - for(int p=2; p<=N; ++p) 41 - if(is_prime(p)) 42 - ++np; 43 - LL v = 1; 44 - for(int i=0; i<np; ++i) 45 - v *= 2; 46 - return v/2; 47 - } 48 - 49 - bool is_prime(int n) 50 - { 51 - for(int k=2; k<n; ++k) 52 - if(n%k == 0) 53 - return false; 54 - return true; 55 - } 56 -}; 57 - 58 -// BEGIN CUT HERE 59 -#include <ctime> 60 -double start_time; string timer() 61 - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 62 -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 63 - { os << "{ "; 64 - for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 65 - os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 66 -void verify_case(const long long& Expected, const long long& Received) { 67 - bool ok = (Expected == Received); 68 - if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 69 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 70 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 71 -#define END verify_case(_, EllysFractions().getCount(N));} 72 -int main(){ 73 - 74 -CASE(0) 75 - int N = 1; 76 - long long _ = 0LL; 77 -END 78 -CASE(1) 79 - int N = 2; 80 - long long _ = 1LL; 81 -END 82 -CASE(2) 83 - int N = 3; 84 - long long _ = 3LL; 85 -END 86 -CASE(3) 87 - int N = 5; 88 - long long _ = 9LL; 89 -END 90 -CASE(4) 91 - int N = 100; 92 - long long _ = 177431885LL; 93 -END 94 -CASE(5) 95 - int N = 250; 96 - long long _ = -1LL; 97 -END 98 -CASE(6) 99 - int N = 4; 100 - long long _ = 5LL; 101 -END 102 -} 103 -// END CUT HERE
Deleted SRM/TCO12-1/1C.cpp version [add6efd3494f287b]
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 <cstring> 18 -#ifdef __GNUC__ 19 -#include <ext/hash_map> 20 -#define unordered_map __gnu_cxx::hash_map 21 -#else 22 -#include <unordered_map> 23 -#endif 24 -using namespace std; 25 -typedef long long LL; 26 -typedef complex<double> CMP; 27 - 28 -struct UnionFind 29 -{ 30 - vector<int> uf, sz; 31 - int nc; 32 - 33 - UnionFind(int N): uf(N), sz(N,1), nc(N) 34 - { for(int i=0; i<N; ++i) uf[i] = i; } 35 - int size() 36 - { return nc; } 37 - int Find(int a) 38 - { return uf[a]==a ? a : uf[a]=Find(uf[a]); } 39 - bool Union(int a, int b) 40 - { 41 - a = Find(a); 42 - b = Find(b); 43 - if( a != b ) 44 - { 45 - if( sz[a] >= sz[b] ) swap(a, b); 46 - uf[a] = b; 47 - sz[b] += sz[a]; 48 - --nc; 49 - } 50 - return (a!=b); 51 - } 52 -}; 53 - 54 -class EllysLights { public: 55 - int getMinimum(string initial, vector <string> switches) 56 - { 57 - int N = switches.size(); 58 - UnionFind uf(N*2+2); 59 - #define TR 0 60 - #define FL 1 61 - #define POS(x) ((x)+2) 62 - #define NEG(x) ((x)+N+2) 63 - 64 - for(int i=0; i<initial.size(); ++i) 65 - { 66 - vector<int> sw; 67 - for(int k=0; k<N; ++k) 68 - if( switches[k][i]=='Y' ) 69 - sw.push_back(k); 70 - 71 - if(initial[i] == 'Y') 72 - if(sw.size() == 0) 73 - { 74 - return -1; 75 - } 76 - else if(sw.size() == 1) 77 - { 78 - uf.Union(POS(sw[0]), TR); 79 - uf.Union(NEG(sw[0]), FL); 80 - } 81 - else 82 - { 83 - uf.Union(POS(sw[0]), NEG(sw[1])); 84 - uf.Union(NEG(sw[0]), POS(sw[1])); 85 - } 86 - else 87 - if(sw.size() == 0) 88 - { 89 - } 90 - else if(sw.size() == 1) 91 - { 92 - uf.Union(POS(sw[0]), FL); 93 - uf.Union(NEG(sw[0]), TR); 94 - } 95 - else 96 - { 97 - uf.Union(POS(sw[0]), POS(sw[1])); 98 - uf.Union(NEG(sw[0]), NEG(sw[1])); 99 - } 100 - } 101 - 102 - if( uf.Find(TR) == uf.Find(FL) ) 103 - return -1; 104 - for(int k=0; k<N; ++k) 105 - if( uf.Find(POS(k)) == uf.Find(NEG(k)) ) 106 - return -1; 107 - 108 - int minSwitch = 0; 109 - set<int> done; 110 - for(int k=0; k<N; ++k) 111 - if( !done.count(k) ) 112 - { 113 - vector<int> pos(1, k); 114 - vector<int> neg; 115 - for(int j=k+1; j<N; ++j) 116 - if( !done.count(j) ) 117 - if( uf.Find(POS(k)) == uf.Find(POS(j)) ) { 118 - pos.push_back(j); 119 - done.insert(j); 120 - } else if( uf.Find(POS(k)) == uf.Find(NEG(j)) ) { 121 - neg.push_back(j); 122 - done.insert(j); 123 - } 124 - if( uf.Find(POS(k)) == uf.Find(TR) ) { 125 - minSwitch += pos.size(); 126 - } 127 - else if( uf.Find(POS(k)) == uf.Find(FL) ) { 128 - minSwitch += neg.size(); 129 - } 130 - else { 131 - minSwitch += min(pos.size(), neg.size()); 132 - } 133 - } 134 - return minSwitch; 135 - } 136 -}; 137 - 138 -// BEGIN CUT HERE 139 -#include <ctime> 140 -double start_time; string timer() 141 - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 142 -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 143 - { os << "{ "; 144 - for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 145 - os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 146 -void verify_case(const int& Expected, const int& Received) { 147 - bool ok = (Expected == Received); 148 - if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 149 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 150 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 151 -#define END verify_case(_, EllysLights().getMinimum(initial, switches));} 152 -int main(){ 153 - 154 -CASE(0) 155 - string initial = "YNYNNN"; 156 - string switches_[] = {"YNNYNY", "NYYYNN", "YNYNYN", "NNNNYN", "NYNNNY"}; 157 - vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 158 - int _ = 2; 159 -END 160 -CASE(1) 161 - string initial = "YNYNYN"; 162 - string switches_[] = {"NNNNNN", "YYYYYY", "NYNNNN", "NNNYNN", "NNNNNY"}; 163 - vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 164 - int _ = 4; 165 -END 166 -CASE(2) 167 - string initial = "YYN"; 168 - string switches_[] = {"YNY", "NYN"}; 169 - vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 170 - int _ = -1; 171 -END 172 -CASE(3) 173 - string initial = "NNYNYNYYYNNYYYYN"; 174 - string switches_[] = {"NYNYNYNYNYNYNYNY", 175 - "YNYNYNYNYNYNYNYN", 176 - "NNNNNNNNNNNNNNNN", 177 - "YNNNNNNNNNNNNNNN", 178 - "NYNNNNNNNNNNNNNN", 179 - "NNYNNNNNNNNNNNNN", 180 - "NNNYNNNNNNNNNNNN", 181 - "NNNNYNNNNNNNNNNN", 182 - "NNNNNYNNNNNNNNNN", 183 - "NNNNNNYNNNNNNNNN", 184 - "NNNNNNNYNNNNNNNN", 185 - "NNNNNNNNYNNNNNNN", 186 - "NNNNNNNNNYNNNNNN", 187 - "NNNNNNNNNNYNNNNN", 188 - "NNNNNNNNNNNYNNNN", 189 - "NNNNNNNNNNNNYNNN", 190 - "NNNNNNNNNNNNNYNN", 191 - "NNNNNNNNNNNNNNYN", 192 - "NNNNNNNNNNNNNNNY"}; 193 - vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 194 - int _ = 6; 195 -END 196 -CASE(4) 197 - string initial = "NYNYNYYYNNYYYNNYNNYYYYYNNYNYYYY"; 198 - string switches_[] = {"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", 199 - "NNNNNNNNYNNNYNNNNYYNYNNNNYNNNNN", 200 - "NNNNNNNNNYNNNNNNNNNNNNYNNNNNNNN", 201 - "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNN", 202 - "NYNNNNNNNNNNNNYNNNNNNNNNNNNNNNN", 203 - "NNNNNNNNNNNNNYYNNNNNNNNNNNNNNNY", 204 - "NNNNNNYNNNNNNNNNNNNYNNNNNYNNNNN", 205 - "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", 206 - "YNNNNNNNNNNNNNNNNNNYNNNNNNNNNNN", 207 - "NNNYNNNNNNNNNNNNNNNNNNNYYNNNNNN", 208 - "NYNNNNNNNNNNYNNNNNNNNNNNNNNNYNN", 209 - "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", 210 - "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", 211 - "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNY", 212 - "NNNNNNNNNNYNNNNNNNNNYYYNNNNNNNN", 213 - "NNNYNNNNNNNNNNNNNNNNNNNNNNNYNNN", 214 - "NNNNNNNNYNNNNNNNNNNNNNNNYNNNNNN", 215 - "YNNNYNNNNNNNNNNNNNNNNNNNNNNYNNN", 216 - "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNN", 217 - "NNNNYNNYNNNNNNNNNNNNNNNNNNNNNNN", 218 - "NNNNNNNYNNNYNNNYNNNNNNNNNNNNNYN"}; 219 - vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 220 - int _ = 7; 221 -END 222 -CASE(5) 223 - string initial = "NYNYYNYNYYYYNNYNYNNYYNNNNNYNYNNNNNYNNNYN"; 224 - string switches_[] = {"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNYNNNN", 225 - "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNN", 226 - "NNNNNNNNNYNNNNYNNYNNNNNNNNNNNNNNNNNNNNNN", 227 - "NNNNNNNNNNNNNNNNNNNYNNNNYNNNNNNNYNNNNNNN", 228 - "NNNNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNN", 229 - "NNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNYNNNNNYNN", 230 - "NNNNNNNNNNYNNNNNNNNNNNNNNYNNNNNYNNYNNNNN", 231 - "NNNNNYNNYNNYNNNNNNNNNNNNNNNNNNNNNYNNNNNN", 232 - "YNNNYNNNNNNNNNNNNNYNNNYNNYNNNNNNNYNNNNNN", 233 - "NNNNNNNNNYYNNNNNNNNNNNNYNNNNYNNNNNNNNNNN", 234 - "NNNNNNNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNNNY", 235 - "NNNNNNNNNNNNYNNNNNNNNNNNYNNNNNNNNNNNNNNN", 236 - "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNN", 237 - "NNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNN", 238 - "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", 239 - "NNNNNNNNNNNNNNYNNYNNNNNNNNNNNNNNNNNNNNNN", 240 - "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYYNNY", 241 - "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNN", 242 - "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", 243 - "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", 244 - "NNNNNNNYNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNN", 245 - "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNN", 246 - "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNN", 247 - "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", 248 - "NYNNNNYNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", 249 - "NNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNN", 250 - "NNNNNNNNNNNNYNNYYNNNNNNNNNNNNNNNNNNNNNNN", 251 - "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", 252 - "NNNYNNNNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNN", 253 - "NNNNNNNNYNNNNNNNNNNNNNNNNNNNYNYNNNNNNNNN", 254 - "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNYNNN"}; 255 - vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 256 - int _ = -1; 257 -END 258 -/* 259 -CASE(6) 260 - string initial = ; 261 - string switches_[] = ; 262 - vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 263 - int _ = ; 264 -END 265 -CASE(7) 266 - string initial = ; 267 - string switches_[] = ; 268 - vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 269 - int _ = ; 270 -END 271 -*/ 272 -} 273 -// END CUT HERE
Name change from from SRM/TCO12-1/1A.cpp to SRM/TCO12-1A/1A.cpp.
Name change from from SRM/TCO12-1/1B.cpp to SRM/TCO12-1A/1B.cpp.
Name change from from SRM/TCO12-1/1C.cpp to SRM/TCO12-1A/1C.cpp.
Added SRM/TCO12-2A-U/1A.cpp version [bf3b5407a7b91a66]
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 <cstring> 18 +#ifdef __GNUC__ 19 +#include <ext/hash_map> 20 +#define unordered_map __gnu_cxx::hash_map 21 +#else 22 +#include <unordered_map> 23 +#endif 24 +using namespace std; 25 +typedef long long LL; 26 +typedef complex<double> CMP; 27 + 28 +typedef int vert; 29 +typedef vert edge; 30 +typedef vector<edge> edges; 31 +typedef vector<edges> graph; 32 + 33 +bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) 34 +{ 35 + for(int i=0; i<G[v].size(); ++i) { 36 + vert u = G[v][i]; 37 + if( visited[u] ) continue; 38 + visited[u] = true; 39 + 40 + if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) 41 + { matchTo[v]=u, matchTo[u]=v; return true; } 42 + } 43 + return false; 44 +} 45 + 46 +template<int NV> 47 +int biMatch( graph& G, int L ) 48 +{ 49 + vector<vert> matchTo(G.size(), -1); 50 + int ans = 0; 51 + for(vert v=0; v<L; ++v) { 52 + bool visited[NV] = {}; 53 + if( augment(G, v, matchTo, visited) ) 54 + ++ans; 55 + } 56 + return ans; 57 +} 58 + 59 +class SwitchesAndLamps { public: 60 + int theMin(vector <string> switches, vector <string> lamps) 61 + { 62 + const int N = switches[0].size(); 63 + const int E = switches.size(); 64 + 65 + vector< vector<bool> > uneq(N, vector<bool>(N)); 66 + 67 + vector<LL> id(N, 1); 68 + for(int e=0; e<E; ++e) { 69 + for(int s=0; s<N; ++s) { 70 + id[s] = id[s]*2 + (switches[e][s]=='Y' ? 0 : 1); 71 + for(int l=0; l<N; ++l) { 72 + if( switches[e][s] != lamps[e][l] ) 73 + uneq[s][l] = true; 74 + } 75 + } 76 + } 77 + 78 + graph G(N*2); 79 + for(int s=0; s<N; ++s) 80 + for(int l=0; l<N; ++l) 81 + if( !uneq[s][l] ) 82 + G[s].push_back(N+l); 83 + if( N > biMatch<100>(G, N) ) 84 + return -1; 85 + 86 + map<LL, int> sizes; 87 + int maxSize = 1; 88 + for(int s=0; s<N; ++s) 89 + maxSize = max(maxSize, ++sizes[id[s]]); 90 + return calcNeed(maxSize); 91 + } 92 + 93 + int calcNeed(int maxSize) 94 + { 95 + if( maxSize<=1 ) 96 + return 0; 97 + return 1 + calcNeed((maxSize+1)/2); 98 + } 99 +}; 100 + 101 +// BEGIN CUT HERE 102 +#include <ctime> 103 +double start_time; string timer() 104 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 105 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 106 + { os << "{ "; 107 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 108 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 109 +void verify_case(const int& Expected, const int& Received) { 110 + bool ok = (Expected == Received); 111 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 112 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 113 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 114 +#define END verify_case(_, SwitchesAndLamps().theMin(switches, lamps));} 115 +int main(){ 116 + 117 +CASE(0) 118 + string switches_[] = {"NYNN", "NNYN"}; 119 + vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 120 + string lamps_[] = {"NNNY", "NNYN"}; 121 + vector <string> lamps(lamps_, lamps_+sizeof(lamps_)/sizeof(*lamps_)); 122 + int _ = 1; 123 +END 124 +CASE(1) 125 + string switches_[] = {"YYN", "YNY", "YYN"}; 126 + vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 127 + string lamps_[] = {"YNY", "NYY", "YNY"}; 128 + vector <string> lamps(lamps_, lamps_+sizeof(lamps_)/sizeof(*lamps_)); 129 + int _ = 0; 130 +END 131 +CASE(2) 132 + string switches_[] = {"NYYYNYNNYYYNYNNNNY", 133 + "NYYYNYNNYYYNYNNNNY"}; 134 + vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 135 + string lamps_[] = {"YYYNNNYNNYNYNYNYNY", 136 + "YYYNNNYNNYNYYNNYNY"}; 137 + vector <string> lamps(lamps_, lamps_+sizeof(lamps_)/sizeof(*lamps_)); 138 + int _ = -1; 139 +END 140 +CASE(3) 141 + string switches_[] = {"YYNNN", "NNYYN"}; 142 + vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 143 + string lamps_[] = {"NYNNY", "NNNYY"}; 144 + vector <string> lamps(lamps_, lamps_+sizeof(lamps_)/sizeof(*lamps_)); 145 + int _ = -1; 146 +END 147 +CASE(4) 148 + string switches_[] = {"YNNYNNYNYY", "NYNNYNYNYN", "YNYNYYYYYN", "NNYYNYNYNN"}; 149 + vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 150 + string lamps_[] = {"NYYNYNNYNY", "NYYYNNYNNN", "YYYYNYNNYY", "YNNNNYNYYN"}; 151 + vector <string> lamps(lamps_, lamps_+sizeof(lamps_)/sizeof(*lamps_)); 152 + int _ = 2; 153 +END 154 +CASE(5) 155 +string switches_[] = {"YYNNN", "YNNNN", "NYNNN"}; 156 + vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 157 +string lamps_[] = {"YYNNN", "YNNNN", "NNYNN"}; 158 + vector <string> lamps(lamps_, lamps_+sizeof(lamps_)/sizeof(*lamps_)); 159 + int _ = -1; 160 +END 161 +CASE(6) 162 +string switches_[] = {"YYNNN", "YNNNN", "NYNNN"}; 163 + vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 164 +string lamps_[] = {"YYNNN", "YNNNN", "YNNNN"}; 165 + vector <string> lamps(lamps_, lamps_+sizeof(lamps_)/sizeof(*lamps_)); 166 + int _ = -1; 167 +END 168 +/* 169 +CASE(6) 170 + string switches_[] = ; 171 + vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); 172 + string lamps_[] = ; 173 + vector <string> lamps(lamps_, lamps_+sizeof(lamps_)/sizeof(*lamps_)); 174 + int _ = ; 175 +END 176 +*/ 177 +} 178 +// END CUT HERE
Added SRM/TCO12-2A-U/1B.cpp version [7efed63f7388becb]
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 <cstring> 18 +#ifdef __GNUC__ 19 +#include <ext/hash_map> 20 +#define unordered_map __gnu_cxx::hash_map 21 +#else 22 +#include <unordered_map> 23 +#endif 24 +using namespace std; 25 +typedef long long LL; 26 +typedef complex<double> CMP; 27 + 28 +template<typename T> 29 +struct DP3 30 +{ 31 + int N1, N2, N3; 32 + vector<T> data; 33 + DP3(int N1, int N2, int N3, const T& t = T()) 34 + : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); } 35 + T& operator()(int i1, int i2, int i3) 36 + { return data[ ((i1*N2)+i2)*N3+i3 ]; } 37 + void swap(DP3& rhs) 38 + { data.swap(rhs.data); } 39 +}; 40 + 41 +class CucumberWatering { public: 42 + long long theMin(vector <int> x, int K) 43 + { 44 + const int N = x.size(); 45 + 46 + vector<pair<LL,int> > pts; 47 + for(int i=0; i<N; ++i) 48 + pts.push_back(make_pair(x[i], i)); 49 + sort(pts.begin(), pts.end()); 50 + 51 + DP3<LL> dp(N, K+1, N, -12345678987654321LL); 52 + dp(0, 0, 0) = dp(0, 1, 0) = 0; 53 + for(int i=1; i<N; ++i) 54 + for(int warpUsed=0; warpUsed<=K; ++warpUsed) { 55 + for(int lastWarpPt=0; lastWarpPt<i; ++lastWarpPt) 56 + dp(i,warpUsed,lastWarpPt) = dp(i-1,warpUsed,lastWarpPt); 57 + 58 + LL maxGain = 0; 59 + if( warpUsed > 1 ) 60 + for(int p=0; p<i; ++p) { 61 + LL gain = 0; 62 + LL P = pts[p].first; 63 + LL Q = pts[i].first; 64 + for(int k=1; k<N; ++k) { 65 + LL X = min(x[k-1], x[k]); 66 + LL Y = max(x[k-1], x[k]); 67 + gain += max(0LL, (Y-X) - (abs(X-P) + abs(Y-Q))); 68 + } 69 + maxGain = max(maxGain, dp(i,warpUsed-1,p) + gain); 70 + } 71 + dp(i,warpUsed,i) = maxGain; 72 + } 73 + 74 + LL naive = 0; 75 + for(int i=1; i<N; ++i) 76 + naive += abs(LL(x[i-1]) - LL(x[i])); 77 + 78 + LL maxGain = 0; 79 + for(int w=0; w<=K; ++w) 80 + for(int p=0; p<N; ++p) 81 + maxGain = max(maxGain, dp(N-1,w,p)); 82 + 83 + return naive - maxGain; 84 + } 85 +}; 86 + 87 +// BEGIN CUT HERE 88 +#include <ctime> 89 +double start_time; string timer() 90 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 91 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 92 + { os << "{ "; 93 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 94 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 95 +void verify_case(const long long& Expected, const long long& Received) { 96 + bool ok = (Expected == Received); 97 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 98 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 99 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 100 +#define END verify_case(_, CucumberWatering().theMin(x, K));} 101 +int main(){ 102 + 103 +CASE(0) 104 + int x_[] = {0, 6, 8, 2}; 105 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 106 + int K = 2; 107 + long long _ = 6LL; 108 +END 109 +CASE(1) 110 + int x_[] = {-1000000000, 1000000000, 0}; 111 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 112 + int K = 1; 113 + long long _ = 3000000000LL; 114 +END 115 +CASE(2) 116 + int x_[] = {58, 2012}; 117 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 118 + int K = 50; 119 + long long _ = 0LL; 120 +END 121 +CASE(3) 122 + int x_[] = {9, -3, 14, 6, 5, -9, 32, 7, -5, 26, 2, 11}; 123 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 124 + int K = 3; 125 + long long _ = 58LL; 126 +END 127 +/* 128 +CASE(4) 129 + int x_[] = ; 130 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 131 + int K = ; 132 + long long _ = LL; 133 +END 134 +CASE(5) 135 + int x_[] = ; 136 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 137 + int K = ; 138 + long long _ = LL; 139 +END 140 +*/ 141 +} 142 +// END CUT HERE