Overview
| SHA1 Hash: | 197afdc1d0b79fefc248f11624c656808809ef43 |
|---|---|
| Date: | 2015-03-26 00:59:00 |
| User: | kinaba |
| Comment: | 652 (or was it 653? check later) |
| 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/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
Added 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
Added 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