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], d > 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(); > 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) > 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 > 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() > 119 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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, > 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, > 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, > 158 ,493,434,-405,478,-148,929,251,56,242,929,-78,423,-664,802,251,759,383,-112,-591 > 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,-15 > 161 ,-234,427,945,265,-157,265,715,275,715,-186,337,798,-170,427,706,754,961,286,-21 > 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.s > 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 > 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.b > 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) > 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 > 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() > 80 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 81 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 82 #define END verify_case(_, AkariDaisukiDiv1().countF(Waai, Akari, Daisuki, > 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() < 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) < 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 < 72 void verify_case(const vector <string>& Expected, const vector <string>& Receive < 73 bool ok = (Expected == Received); < 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 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(*pl < 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(*pl < 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(*pl < 94 string __[] = {"elly" }; < 95 vector <string> _(__, __+sizeof(__)/sizeof(*__)); < 96 END < 97 CASE(3) < 98 string players_[] = { "ariadne", "elly", "ariadne", "stancho", "stancho" < 99 vector <string> players(players_, players_+sizeof(players_)/sizeof(*pl < 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(*pl < 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(*pl < 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) < 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 < 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() < 69 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 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(P < 118 pos.push_back(j); < 119 done.insert(j); < 120 } else if( uf.Find(POS(k)) == uf < 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) < 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 < 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() < 149 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 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 < 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 < 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 < 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 < 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 < 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 < 256 int _ = -1; < 257 END < 258 /* < 259 CASE(6) < 260 string initial = ; < 261 string switches_[] = ; < 262 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof < 263 int _ = ; < 264 END < 265 CASE(7) < 266 string initial = ; < 267 string switches_[] = ; < 268 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof < 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) > 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 > 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() > 112 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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 > 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 > 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 > 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 > 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", "NNYYNYN > 149 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 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 > 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 > 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 > 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() > 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,warpU > 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) - > 68 } > 69 maxGain = max(maxGain, dp(i,warp > 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) > 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 > 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() > 98 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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