Overview
| SHA1 Hash: | d649a7e3cab988c2013b56c91b451c2b4b2a2120 |
|---|---|
| Date: | 2015-03-26 01:01:09 |
| User: | kinaba |
| Comment: | It was 653 |
| 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
Deleted SRM/652-U/1A.cpp version [7d9c4ca801a229b3]
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 CountryGroupHard { public: < 23 string solve(vector <int> a) < 24 { < 25 return rec(0, a)==1 ? "Sufficient" : "Insufficient"; < 26 } < 27 < 28 map<int, int> memo; < 29 int rec(int k, const vector<int>& a) < 30 { < 31 if(k == a.size()) < 32 return 1; < 33 if(memo.count(k)) < 34 return memo[k]; < 35 < 36 int cnt = 0; < 37 for(int v=1; k+v<=int(a.size()); ++v) { < 38 set<int> s(a.begin()+k, a.begin()+k+v); < 39 s.erase(0); < 40 s.erase(v); < 41 if(s.empty()) < 42 cnt += rec(k+v, a); < 43 } < 44 return memo[k] = (cnt>=2 ? 2 : cnt); < 45 } < 46 }; < 47 < 48 // BEGIN CUT HERE < 49 #include <ctime> < 50 double start_time; string timer() < 51 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 52 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 53 { os << "{ "; < 54 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 55 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 56 void verify_case(const string& Expected, const string& Received) { < 57 bool ok = (Expected == Received); < 58 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 59 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 60 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 61 #define END verify_case(_, CountryGroupHard().solve(a));} < 62 int main(){ < 63 < 64 CASE(0) < 65 int a_[] = {0,2,3,0,0}; < 66 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); < 67 string _ = "Sufficient"; < 68 END < 69 CASE(1) < 70 int a_[] = {0,2,0}; < 71 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); < 72 string _ = "Insufficient"; < 73 END < 74 CASE(2) < 75 int a_[] = {0,3,0,0,3,0}; < 76 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); < 77 string _ = "Sufficient"; < 78 END < 79 CASE(3) < 80 int a_[] = {0,0,3,3,0,0}; < 81 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); < 82 string _ = "Insufficient"; < 83 END < 84 CASE(4) < 85 int a_[] = {2,2,0,2,2}; < 86 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); < 87 string _ = "Sufficient"; < 88 END < 89 /* < 90 CASE(5) < 91 int a_[] = ; < 92 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); < 93 string _ = ; < 94 END < 95 CASE(6) < 96 int a_[] = ; < 97 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); < 98 string _ = ; < 99 END < 100 */ < 101 } < 102 // END CUT HERE <
Deleted SRM/652-U/1B.cpp version [ffc08068b2a48f88]
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 template<typename T> < 23 class IdGen < 24 { < 25 map<T, int> v2id_; < 26 vector<T> id2v_; < 27 public: < 28 int v2id(const T& v) { < 29 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } < 30 return v2id_[v]; < 31 } < 32 const T& id2v(int i) const { return id2v_[i]; } < 33 int size() const { return id2v_.size(); } < 34 }; < 35 < 36 template<typename Vert=pair<int,int>, typename Flow=LL, int NV=2048> < 37 class MaxFlow < 38 { < 39 IdGen<Vert> idgen; < 40 vector<int> G[NV]; < 41 Flow F[NV][NV]; < 42 < 43 public: < 44 void addEdge( Vert s_, Vert t_, Flow f ) < 45 { < 46 const int s = idgen.v2id(s_), t = idgen.v2id(t_); < 47 G[s].push_back(t); < 48 G[t].push_back(s); < 49 F[s][t] = f; < 50 F[t][s] = 0; < 51 } < 52 < 53 Flow calc( Vert s_, Vert t_ ) < 54 { < 55 const int S = idgen.v2id(s_), D = idgen.v2id(t_); < 56 for( Flow total=0 ;; ) { < 57 // Do BFS and compute the level for each node. < 58 int LV[NV] = {0}; < 59 vector<int> Q(1, S); < 60 for(int lv=1; !Q.empty(); ++lv) { < 61 vector<int> Q2; < 62 for(size_t i=0; i!=Q.size(); ++i) { < 63 const vector<int>& ne = G[Q[i]]; < 64 for(size_t j=0; j!=ne.size(); ++j) < 65 if( F[Q[i]][ne[j]] && !LV[ne[j]] < 66 LV[ne[j]]=lv, Q2.push_ba < 67 } < 68 Q.swap(Q2); < 69 } < 70 < 71 // Destination is now unreachable. Done. < 72 if( !LV[D] ) < 73 return total; < 74 < 75 // Iterating DFS. < 76 bool blocked[NV] = {}; < 77 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); < 78 } < 79 } < 80 < 81 private: < 82 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) < 83 { < 84 Flow flow_out = 0; < 85 for(size_t i=0; i!=G[v].size(); ++i) { < 86 int u = G[v][i]; < 87 if( LV[v]+1==LV[u] && F[v][u] ) { < 88 Flow f = min(flow_in-flow_out, F[v][u]); < 89 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f < 90 F[v][u] -= f; < 91 F[u][v] += f; < 92 flow_out += f; < 93 if( flow_in == flow_out ) return flow_ou < 94 } < 95 } < 96 } < 97 blocked[v] = (flow_out==0); < 98 return flow_out; < 99 } < 100 }; < 101 < 102 class Singing { public: < 103 int solve(int N, int low, int high, vector <int> pitch) < 104 { < 105 map<pair<int,int>, int> edge; < 106 for(int i=0; i+1<pitch.size(); ++i) { < 107 int p0 = min(pitch[i], pitch[i+1]); < 108 int p1 = max(pitch[i], pitch[i+1]); < 109 if(p0 != p1) < 110 edge[make_pair(p0,p1)] ++; < 111 } < 112 < 113 MaxFlow<>* mf = new MaxFlow<>; < 114 const LL INF = 0x3fffffff; < 115 < 116 enum{BOB, LEFT, RIGHT, ALICE}; < 117 pair<int,int> Bob(BOB,0); < 118 pair<int,int> Alice(ALICE,0); < 119 for(int v=1; v<=N; ++v) { < 120 if(v>high) < 121 mf->addEdge(Bob, make_pair(LEFT,v), INF); < 122 mf->addEdge(make_pair(LEFT,v), make_pair(RIGHT,v), INF); < 123 if(v<low) < 124 mf->addEdge(make_pair(RIGHT,v), Alice, INF); < 125 } < 126 for(auto e: edge) { < 127 int v = e.first.first; < 128 int u = e.first.second; < 129 int c = e.second; < 130 mf->addEdge(make_pair(RIGHT,v), make_pair(LEFT,u), c); < 131 mf->addEdge(make_pair(RIGHT,u), make_pair(LEFT,v), c); < 132 } < 133 < 134 LL ans = mf->calc(Bob, Alice); < 135 delete mf; < 136 return int(ans); < 137 } < 138 }; < 139 < 140 // BEGIN CUT HERE < 141 #include <ctime> < 142 double start_time; string timer() < 143 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 144 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 145 { os << "{ "; < 146 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 147 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 148 void verify_case(const int& Expected, const int& Received) { < 149 bool ok = (Expected == Received); < 150 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 151 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 152 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 153 #define END verify_case(_, Singing().solve(N, low, high, pitch));} < 154 int main(){ < 155 < 156 CASE(0) < 157 int N = 3; < 158 int low = 2; < 159 int high = 2; < 160 int pitch_[] = {1,2,3,2,1,2}; < 161 vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); < 162 int _ = 2; < 163 END < 164 CASE(1) < 165 int N = 10; < 166 int low = 3; < 167 int high = 7; < 168 int pitch_[] = {4,4,5,5,6,5,3,6}; < 169 vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); < 170 int _ = 0; < 171 END < 172 CASE(2) < 173 int N = 6; < 174 int low = 2; < 175 int high = 5; < 176 int pitch_[] = {5,3,1,6,4,2}; < 177 vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); < 178 int _ = 1; < 179 END < 180 CASE(3) < 181 int N = 10; < 182 int low = 4; < 183 int high = 5; < 184 int pitch_[] = {1,4,3,5,2,5,7,5,9}; < 185 vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); < 186 int _ = 3; < 187 END < 188 CASE(4) < 189 int N = 100; < 190 int low = 20; < 191 int high = 80; < 192 int pitch_[] = {2,27,3,53,53,52,52,60,85,89,100,53,60,2,3,53,100,89,40,4 < 193 vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); < 194 int _ = 5; < 195 END < 196 /* < 197 CASE(5) < 198 int N = ; < 199 int low = ; < 200 int high = ; < 201 int pitch_[] = ; < 202 vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); < 203 int _ = ; < 204 END < 205 CASE(6) < 206 int N = ; < 207 int low = ; < 208 int high = ; < 209 int pitch_[] = ; < 210 vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); < 211 int _ = ; < 212 END < 213 */ < 214 } < 215 // END CUT HERE <
Deleted SRM/652-U/1C-U.cpp version [f01284ac275c4ca0]
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 static const unsigned MODVAL = 1000000007; < 23 struct mint < 24 { < 25 unsigned val; < 26 mint():val(0){} < 27 mint(int x):val(x%MODVAL) {} < 28 mint(unsigned x):val(x%MODVAL) {} < 29 mint(LL x):val(x%MODVAL) {} < 30 }; < 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } < 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } < 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } < 34 mint operator+(mint x, mint y) { return x+=y; } < 35 mint operator-(mint x, mint y) { return x-=y; } < 36 mint operator*(mint x, mint y) { return x*=y; } < 37 < 38 // nCk :: O(1) time, O(n^2) space. < 39 vector< vector<mint> > CP_; < 40 mint C(int n, int k) { < 41 while( CP_.size() <= n ) { < 42 int nn = CP_.size(); < 43 CP_.push_back(vector<mint>(nn+1,1)); < 44 for(int kk=1; kk<nn; ++kk) < 45 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; < 46 } < 47 return k<0 || n<k ? 0 : CP_[n][k]; < 48 } < 49 < 50 typedef tuple<int,int,int> Vec; < 51 inline int operator*(Vec v, Vec u) { < 52 return get<0>(v)*get<0>(u) + get<1>(v)*get<1>(u) + get<2>(v)*get<2>(u); < 53 } < 54 < 55 class RockPaperScissorsMagic { public: < 56 int count(int W, int L, int T, vector <int> card) < 57 { < 58 const int N0 = std::count(card.begin(), card.end(), 0); < 59 const int N1 = std::count(card.begin(), card.end(), 1); < 60 const int N2 = std::count(card.begin(), card.end(), 2); < 61 < 62 mint ans = 0; < 63 for(int x1=0; x1<=N0; ++x1) < 64 for(int x2=0; x1+x2<=N0; ++x2) < 65 for(int y1=0; y1<=N1; ++y1) < 66 for(int y2=0; y1+y2<=N1; ++y2) < 67 for(int z1=0; z1<=N2; ++z1) < 68 for(int z2=0; z1+z2<=N2; ++z2) { < 69 int x3,y3,z3; < 70 Vec x(x1, x2, x3=N0-x1-x2); < 71 Vec y(y1, y2, y3=N1-y1-y2); < 72 Vec z(z1, z2, z3=N2-z1-z2); < 73 Vec TLW(T,L,W); < 74 Vec WTL(W,T,L); < 75 Vec LTW(L,T,W); < 76 if(TLW*x+WTL*y != TLW*y+WTL*x) continue; < 77 if(T!=L && x1-x2!=y1-y2) continue; < 78 if(W!=L && x1-x3!=y1-y3) continue; < 79 if(TLW*x+WTL*z != TLW*z+WTL*x) continue; < 80 if(T!=L && x1-x2!=z1-z2) continue; < 81 if(W!=L && x1-x3!=z1-z3) continue; < 82 < 83 ans += C(N0, x1) * C(N0-x1, x2) < 84 * C(N1, y1) * C(N1-y1, y2) < 85 * C(N2, z1) * C(N2-z1, z2); < 86 } < 87 return ans.val; < 88 } < 89 }; < 90 < 91 // BEGIN CUT HERE < 92 #include <ctime> < 93 double start_time; string timer() < 94 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 95 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 96 { os << "{ "; < 97 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 98 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 99 void verify_case(const int& Expected, const int& Received) { < 100 bool ok = (Expected == Received); < 101 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 102 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 103 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 104 #define END verify_case(_, RockPaperScissorsMagic().count(win, lose, tie, c < 105 int main(){ < 106 < 107 CASE(0) < 108 int win = 2; < 109 int lose = 0; < 110 int tie = 1; < 111 int card_[] = {0,1,2}; < 112 vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_)); < 113 int _ = 3; < 114 END < 115 CASE(1) < 116 int win = 2; < 117 int lose = 0; < 118 int tie = 1; < 119 int card_[] = {0,0,0}; < 120 vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_)); < 121 int _ = 6; < 122 END < 123 CASE(2) < 124 int win = 0; < 125 int lose = 0; < 126 int tie = 0; < 127 int card_[] = {1,0,2,2,2,0}; < 128 vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_)); < 129 int _ = 729; < 130 END < 131 CASE(3) < 132 int win = 514; < 133 int lose = 451; < 134 int tie = 145; < 135 int card_[] = {0,0,0,0,0,1,1,1,1,1,1,2,2,2}; < 136 vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_)); < 137 int _ = 0; < 138 END < 139 CASE(4) < 140 int win = 3; < 141 int lose = 6; < 142 int tie = 9; < 143 int card_[] = {0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2}; < 144 vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_)); < 145 int _ = 2336040; < 146 END < 147 CASE(5) < 148 int win = 514; < 149 int lose = 451; < 150 int tie = 145; < 151 int card_[] = {0,0,0,1,1,1,1,1,1,2,2,2,2,2,2}; < 152 vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_)); < 153 int _ = 116100; < 154 END < 155 /* < 156 CASE(6) < 157 int win = ; < 158 int lose = ; < 159 int tie = ; < 160 int card_[] = ; < 161 vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_)); < 162 int _ = ; < 163 END < 164 CASE(7) < 165 int win = ; < 166 int lose = ; < 167 int tie = ; < 168 int card_[] = ; < 169 vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_)); < 170 int _ = ; < 171 END < 172 */ < 173 } < 174 // END CUT HERE <
Name change from from SRM/652-U/1A.cpp to SRM/653-U/1A.cpp.
Name change from from SRM/652-U/1B.cpp to SRM/653-U/1B.cpp.
Name change from from SRM/652-U/1C-U.cpp to SRM/653-U/1C-U.cpp.