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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 59 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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]] && ne[j]!=S ) 66 - LV[ne[j]]=lv, Q2.push_back(ne[j]); 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,blocked))>0 ) { 90 - F[v][u] -= f; 91 - F[u][v] += f; 92 - flow_out += f; 93 - if( flow_in == flow_out ) return flow_out; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 151 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,42,2,53,2,85}; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 102 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 103 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 104 -#define END verify_case(_, RockPaperScissorsMagic().count(win, lose, tie, card));} 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.