Overview
| SHA1 Hash: | 892764d484cdbac0c0cac8280e8ce9ca3becc002 |
|---|---|
| Date: | 2014-09-17 14:57:06 |
| User: | kinaba |
| Comment: | 632 |
| 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/632-U/1A.cpp version [716106b188541b81]
> 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 PotentialArithmeticSequence { public: > 23 int numberOfSubsequences(vector <int> d) > 24 { > 25 int cnt = 0; > 26 for(int s=0; s<d.size(); ++s) > 27 for(int e=s+1; e<=d.size(); ++e) > 28 if(incr(vector<int>(d.begin()+s, d.begin()+e))) > 29 ++cnt; > 30 return cnt; > 31 } > 32 > 33 bool incr(vector<int> d) > 34 { > 35 int mi = max_element(d.begin(), d.end()) - d.begin(); > 36 int& M = d[mi]; > 37 > 38 // Can assume a[mi] == 1<<M. > 39 M = min(M, 8); > 40 for(int i=0; i<d.size(); ++i) { > 41 int a = (1<<M)-mi+i; > 42 if(a<=0) > 43 return false; > 44 if(d[i]>M) > 45 return false; > 46 if(((a>>d[i])&1) == 0) > 47 return false; > 48 if(a & ((1<<d[i])-1)) > 49 return false; > 50 } > 51 return true; > 52 } > 53 }; > 54 > 55 // BEGIN CUT HERE > 56 #include <ctime> > 57 double start_time; string timer() > 58 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 59 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 60 { os << "{ "; > 61 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 62 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 63 void verify_case(const int& Expected, const int& Received) { > 64 bool ok = (Expected == Received); > 65 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 66 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 67 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 68 #define END verify_case(_, PotentialArithmeticSequence().numberOfSubsequenc > 69 int main(){ > 70 > 71 CASE(0) > 72 int d_[] = {0,1,0,2,0,1,0}; > 73 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 74 int _ = 28; > 75 END > 76 CASE(1) > 77 int d_[] = {0,0,0,0,0,0,0}; > 78 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 79 int _ = 7; > 80 END > 81 CASE(2) > 82 int d_[] = {0,0,0,0,1,1,1}; > 83 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 84 int _ = 8; > 85 END > 86 CASE(3) > 87 int d_[] = {0,100,0,2,0}; > 88 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 89 int _ = 11; > 90 END > 91 CASE(4) > 92 int d_[] = {1,11,3,0,1,0,1,0,1,0,1,0,3,0,2,0,0,0,0,1,2,3,20}; > 93 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 94 int _ = 49; > 95 END > 96 /* > 97 CASE(5) > 98 int d_[] = ; > 99 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 100 int _ = ; > 101 END > 102 CASE(6) > 103 int d_[] = ; > 104 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 105 int _ = ; > 106 END > 107 */ > 108 } > 109 // END CUT HERE
Added SRM/632-U/1B-U.cpp version [2e1145b0d110a2f1]
> 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 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 38 > 39 class CandyCupRunningCompetition { public: > 40 int findMaximum(int N, vector <int> A, vector <int> B) > 41 { > 42 const int START = 0, GOAL = N-1; > 43 typedef mint Flow; > 44 typedef int FlowFlag; > 45 > 46 vector<vector<FlowFlag>> FF(N, vector<FlowFlag>(N, 0)); > 47 vector<vector<Flow>> F(N, vector<Flow>(N, 0)); > 48 vector<vector<int>> G(N); > 49 for(int i=0; i<A.size(); ++i) { > 50 int a = A[i], b = B[i]; > 51 FF[a][b] = FF[b][a] = i+1; > 52 F[a][b] = F[b][a] = POW(3, i); > 53 G[a].push_back(b); > 54 G[b].push_back(a); > 55 } > 56 > 57 Flow total = 0; > 58 for(;;) { > 59 // BFS > 60 vector<int> prev(N, -1); > 61 queue<int> q; > 62 prev[START] = START; > 63 q.push(START); > 64 > 65 while(!q.empty()) { > 66 int u = q.front(); q.pop(); > 67 for(int v: G[u]) if(prev[v]==-1 && FF[u][v]) { > 68 q.push(v); > 69 prev[v] = u; > 70 if(v == GOAL) > 71 goto endBfs; > 72 } > 73 } > 74 endBfs: > 75 if(prev[GOAL] == -1) > 76 break; // no more flow > 77 > 78 Flow f; > 79 FlowFlag ff = 0x7fffffff; > 80 for(int v=GOAL; v!=prev[v]; v=prev[v]) { > 81 int u = prev[v]; > 82 if(FF[u][v] < ff) { > 83 ff = FF[u][v]; > 84 f = F[u][v]; > 85 } > 86 } > 87 > 88 total += f; > 89 for(int v=GOAL; v!=prev[v]; v=prev[v]) { > 90 int u = prev[v]; > 91 F[u][v] -= f; > 92 F[v][u] += f; > 93 if(FF[u][v] == ff) { > 94 FF[u][v] = 0; > 95 FF[v][u] = ff; > 96 } > 97 } > 98 } > 99 return total.val; > 100 } > 101 }; > 102 > 103 // BEGIN CUT HERE > 104 #include <ctime> > 105 double start_time; string timer() > 106 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 107 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 108 { os << "{ "; > 109 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 110 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 111 void verify_case(const int& Expected, const int& Received) { > 112 bool ok = (Expected == Received); > 113 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 114 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 115 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 116 #define END verify_case(_, CandyCupRunningCompetition().findMaximum(N, A, B > 117 int main(){ > 118 CASE(0) > 119 int N = 3; > 120 int A_[] = {0,1}; > 121 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 122 int B_[] = {1,2}; > 123 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 124 int _ = 1; > 125 END > 126 CASE(1) > 127 int N = 4; > 128 int A_[] = {0,1,0,2}; > 129 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 130 int B_[] = {1,3,2,3}; > 131 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 132 int _ = 10; > 133 END > 134 CASE(2) > 135 int N = 3; > 136 int A_[] = {0}; > 137 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 138 int B_[] = {1}; > 139 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 140 int _ = 0; > 141 END > 142 CASE(3) > 143 int N = 5; > 144 vector <int> A; > 145 vector <int> B; > 146 int _ = 0; > 147 END > 148 CASE(4) > 149 int N = 6; > 150 int A_[] = {1,1,2,0,4,3,0,1,4}; > 151 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 152 int B_[] = {3,2,3,1,5,5,2,4,3}; > 153 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 154 int _ = 39; > 155 END > 156 /* > 157 CASE(5) > 158 int N = ; > 159 int A_[] = ; > 160 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 161 int B_[] = ; > 162 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 163 int _ = ; > 164 END > 165 CASE(6) > 166 int N = ; > 167 int A_[] = ; > 168 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 169 int B_[] = ; > 170 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 171 int _ = ; > 172 END > 173 */ > 174 } > 175 // END CUT HERE
Added SRM/632-U/1C-U.cpp version [5157fbd0866d284e]
> 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 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 class PatternLock { public: > 39 int solve(int N, int MOD) > 40 { > 41 MODVAL = MOD; > 42 memo.resize(N+1, vector<int>(N+1, -1)); > 43 return (rec(N,N)*2) % MOD; > 44 } > 45 > 46 vector<vector<int>> memo; > 47 int rec(int A, int B) > 48 { > 49 if(memo[A][B] != -1) > 50 return memo[A][B]; > 51 mint total; > 52 for(int a=0; a<A; ++a) > 53 total += rec(A, B, a); > 54 return memo[A][B] = total.val; > 55 } > 56 int rec(int A, int B, int a) > 57 { > 58 if(A==1 && B==0) > 59 return 1; > 60 > 61 mint total; > 62 if(B) total += rec(B, A-1); > 63 if(a>0) total += rec(A-1, B, a-1); > 64 if(a!=A-1) total += rec(A-1, B, a); > 65 return total.val; > 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(_, PatternLock().solve(N, MOD));} > 83 int main(){ > 84 /* > 85 CASE(0) > 86 int N = 1; > 87 int MOD = 12345667; > 88 int _ = 2; > 89 END > 90 */ > 91 CASE(1) > 92 int N = 2; > 93 int MOD = 324124124; > 94 int _ = 24; > 95 END > 96 CASE(2) > 97 int N = 3; > 98 int MOD = 5325352; > 99 int _ = 504; > 100 END > 101 CASE(3) > 102 int N = 500; > 103 int MOD = 1000000007; > 104 int _ = 286169049; > 105 END > 106 /* > 107 CASE(4) > 108 int N = ; > 109 int MOD = ; > 110 int _ = ; > 111 END > 112 CASE(5) > 113 int N = ; > 114 int MOD = ; > 115 int _ = ; > 116 END > 117 */ > 118 } > 119 // END CUT HERE